烧饼排序

烧饼排序是个很有意思的实际问题：假设盘子上有 n 块面积大小不一 的烧饼，你如何用一把锅铲进行若干次翻转，让这些烧饼的大小有序（小的在上，大的在下）？ 烧饼排序 - 图1 设想一下用锅铲翻转一堆烧饼的情景，其实是有一点限制的，我们每次只能将最上面的若干块饼子翻转： 烧饼排序 - 图2 我们的问题是，如何使用算法得到一个翻转序列，使得烧饼堆变得有序 ？ 首先，需要把这个问题抽象，用数组来表示烧饼堆： 烧饼排序 - 图3 如何解决这个问题呢？其实类似上篇文章 递归反转链表的一部分，这也是需要递归思想 的。

一、思路分析

为什么说这个问题有递归性质呢？比如说我们需要实现这样一个函数：

  1.   1. // cakes 是一堆烧饼，函数会将前 n 个烧饼排序
  2.     2. void sort(int[] cakes, int n);

如果我们找到了前 n 个烧饼中最大的那个，然后设法将这个饼子翻转到最底下： 烧饼排序 - 图4 那么，原问题的规模就可以减小，递归调用 pancakeSort(A, n-1) 即可： 烧饼排序 - 图5 接下来，对于上面的这 n - 1 块饼，如何排序呢？还是先从中找到最大的一块饼，然后把这块饼放到底下，再递归调用 pancakeSort(A, n-1-1)…… 你看，这就是递归性质，总结一下思路就是： 1、找到 n 个饼中最大的那个。 2、把这个最大的饼移到最底下。 3、递归调用 pancakeSort(A, n - 1)。 base case：n == 1 时，排序 1 个饼时不需要翻转。 那么，最后剩下个问题，如何设法将某块烧饼翻到最后呢 ？ 其实很简单，比如第 3 块饼是最大的，我们想把它换到最后，也就是换到第 n 块。可以这样操作： 1、用锅铲将前 3 块饼翻转一下，这样最大的饼就翻到了最上面。 2、用锅铲将前 n 块饼全部翻转，这样最大的饼就翻到了第 n 块，也就是最后一块。 以上两个流程理解之后，基本就可以写出解法了，不过题目要求我们写出具体的反转操作序列，这也很简单，只要在每次翻转烧饼时记录下来就行了。

二、代码实现

只要把上述的思路用代码实现即可，唯一需要注意的是，数组索引从 0 开始，而我们要返回的结果是从 1 开始算的。

  1.   1. // 记录反转操作序列
  2.     2. LinkedList<Integer> res = new LinkedList<>();
  3.     3.   4. List<Integer> pancakeSort(int[] cakes) {
  4.     5.     sort(cakes, cakes.length);
  5.     6.     return res;
  6.     7. }
  7.     8.   9. void sort(int[] cakes, int n) {
  8.     10.     // base case
  9.     11.     if (n == 1) return;
  10.     12.   13.     // 寻找最大饼的索引
  11.     14.     int maxCake = 0;
  12.     15.     int maxCakeIndex = 0;
  13.     16.     for (int i = 0; i < n; i++)
  14.     17.         if (cakes[i] > maxCake) {
  15.     18.             maxCakeIndex = i;
  16.     19.             maxCake = cakes[i];
  17.     20.         }
  18.     21.   22.     // 第一次翻转，将最大饼翻到最上面
  19.     23.     reverse(cakes, 0, maxCakeIndex);
  20.     24.     res.add(maxCakeIndex + 1);
  21.     25.     // 第二次翻转，将最大饼翻到最下面
  22.     26.     reverse(cakes, 0, n - 1);
  23.     27.     res.add(n);
  24.     28.   29.     // 递归调用
  25.     30.     sort(cakes, n - 1);
  26.     31. }
  27.     32.   33. void reverse(int[] arr, int i, int j) {
  28.     34.     while (i < j) {
  29.     35.         int temp = arr[i];
  30.     36.         arr[i] = arr[j];
  31.     37.         arr[j] = temp;
  32.     38.         i++; j--;
  33.     39.     }
  34.     40. }

通过刚才的详细解释，这段代码应该是很清晰了。 算法的时间复杂度很容易计算，因为递归调用的次数是 n，每次递归调用都需要一次 for 循环，时间复杂度是 O(n)，所以总的复杂度是 O(n^2)。 最后，我们可以思考一个问题​ ：按照我们这个思路，得出的操作序列长度应该为​ 2(n - 1)，因为每次递归都要进行 2 次翻转并记录操作，总共有 n 层递归，但由于 base case 直接返回结果，不进行翻转，所以最终的操作序列长度应该是固定的 2(n - 1)。 显然，这个结果不是最优的（最短的），比如说一堆煎饼 [3,2,4,1]，我们的算法得到的翻转序列是 [3,4,2,3,1,2]，但是最快捷的翻转方法应该是 [2,3,4]： 初始状态 ：[3,2,4,1]
翻前 2 个：[2,3,4,1]
翻前 3 个：[4,3,2,1]
翻前 4 个：[1,2,3,4] 如果要求你的算法计算排序烧饼的最短 操作序列，你该如何计算呢？或者说，解决这种求最优解法的问题，核心思路什么，一定需要使用什么算法技巧呢？ 不妨分享一下你的思考。 坚持原创高质量文章，致力于把算法问题讲清楚，欢迎关注我的公众号 labuladong 获取最新文章： labuladong 上一篇：拆解复杂问题：实现计算器 下一篇：前缀和技巧 目录

整理人：豆包AI助手