九章算法 | 烙饼排序

给一个 无序数组，对其排序。只能对数组执行以下操作。

        flip(arr, i): 翻转数组中下标从 0 到 i 的元素
      

与传统的排序算法不同，传统的排序算法试图以尽可能少的比较进行排序。我们的目标是用尽可能少的翻转来实现排序。

在线评测地址：LintCode 领扣

样例 1:

        输入: array = [6,11,10,12,7,23,20]
输出：[6,7,10,11,12,20,23]
解释：
flip(array, 5)
flip(array, 6)
flip(array, 0)
flip(array, 5)
flip(array, 1)
flip(array, 4)
flip(array, 1)
flip(array, 3)
flip(array, 1)
flip(array, 2)
      

样例 2:

        输入: array = [4, 2, 3]
输出: array = [2, 3, 4]
解释:
	flip(array, 2)
	flip(array, 1)
      

【题解】

算法：思维

• 这题就是寻找当前未确定位置的数的范围内的的最大值，进行两次翻转。
  • 先翻转将最大值放到首位，然后再翻转将最大值放到尾部即已被排序部分（假设第一次反转排序，我们找到最大值，下标为index1，我们通过第一次翻转，将index1的数翻转到0，再通过第二次翻转，从0翻转到最后一位），寻找范围变小，
• 下一次继续寻找被确定范围内的最大值....一直重复直到序列有序
• 从左向右遍历，当前未被确定的范围为[0,len]，确定是最大的且排好序的范围为[len+1,n]
• 查询当前范围[0,len]的最大值，其位置为pos
• 通过第一次反转[0,pos], 将范围内最大值放到首部
• 通过第一次反转[0,len], 将范围内最大值放到尾部
• 未被确定的范围更新为[0,len-1]，重复上面的步骤

复杂度分析

• 时间复杂度O(n*n)
  • 最多交换n*n次
• 空间复杂度O(1)
  • 不用额外空间

         public class Solution {
    /**
     * @param array: an integer array
     * @return: nothing
     */
    public void pancakeSort(int[] array) {
        int len = array.length;
        if (array == null || len == 0) {
            return;
        }
        while (len>0) {
            int maxIndex = 0;
            for (int index = 0; index < len; index++) { 
                // 找下一个更大的元素
                if (array[maxIndex] < array[index]) {
                    maxIndex = index;
                }
            }
            if(maxIndex == len - 1){
            //如果当前最大数已经在目标位置，则无需翻转
                len--;
                continue;
            }
            // 翻转较大的元素到当前第一个索引的左侧
            if(maxIndex != 0){
                FlipTool.flip(array,maxIndex);
            }
            // 将首部元素翻转到尾部
            len--;
            FlipTool.flip(array,len);
        }
    }
}
      

更多题解参见：九章算法