煎饼排序
难度:中等
通过翻转,我们可以将最大值放到最右边的位置。
具体实现:每次获取剩余数组中的最大值下标,判断当前下标是否在最右侧,若在最右侧则无需处理,若不在最右侧则分为两种情况
- 该最大值在第一位,则只需要一次翻转即可将该值置于最右侧
- 该最大值不在第一位,则将起始位置到该值所处位置的元素翻转,此时最大值将会成为第一位,再重复步骤1。
代码如下:
public List<Integer> pancakeSort(int[] arr) {
List<Integer> res = new ArrayList<>();
int r = arr.length-1;
while(r>0){
int idx = max(arr, r);
if (idx==r){
r--;
continue;
}
if (idx!=0){
reverse(arr,idx);
res.add(idx+1);
}
reverse(arr,r);
res.add(r+1);
r--;
}
return res;
}
//将arr数组的前r位翻转
private void reverse(int[] arr, int r) {
int pre = 0;
int end = r;
while(pre<end){
arr[end] = arr[pre] ^ arr[end];
arr[pre] = arr[pre] ^ arr[end];
arr[end] = arr[pre] ^ arr[end];
pre++;
end--;
}
}
//求arr数组前k位的最大值下标
public int max(int[] arr,int k){
int idx = 0;
for (int i = 1; i <= k; i++) {
if (arr[i]>arr[idx]) idx = i;
}
return idx;
}
执行结果:成功