递归思想用锅铲给烧饼排序

（给算法爱好者加星标，修炼编程内功）

来源：labuladong

烧饼排序是个很有意思的实际问题：假设盘子上有n块面积大小不一的烧饼，你如何用一把锅铲进行若干次翻转，让这些烧饼的大小有序（小的在上，大的在下）？

设想一下用锅铲翻转一堆烧饼的情景，其实是有一点限制的，我们每次只能将最上面的若干块饼子同时翻转：

我们的问题是，如何使用算法得到一个翻转序列，使得烧饼堆变得有序？

首先，这个问题可以抽象成一道算法题，用数组来表示烧饼堆：

如何解决这个问题呢？其实类似上篇文章递归思维：k个一组反转链表，这也是需要递归思想的。

一、思路分析

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

//caks是一堆烧饼，函数会将最上面n个烧饼排序voidsort(int[]caks,intn);

如果我们找到了前n个烧饼中最大的那个，然后设法将这个饼子翻转到最底下：

那么，原问题的规模就可以减小，只需要排序剩下的n-1块饼就行了。也就是说递归调用pancakSort(A,n-1)即可：

接下来，对于上面的这n-1块饼，如何排序呢？还是先从中找到最大的一块饼，然后把这块饼放到底下，再递归调用pancakSort(A,n-1-1)……

你看，这就是递归性质，总结一下思路就是：

1、找到n个饼中最大的那个。

2、把这个最大的饼移到最底下。

、递归调用pancakSort(A,n-1)。

bascas：n==1时，排序1个饼时不需要翻转。

那么，最后剩下个问题，如何设法将某块烧饼翻到最后呢？

其实很简单，比如第块饼是最大的，我们想把它换到最后，也就是换到第n块。可以这样操作：

1、用锅铲将前块饼翻转一下，这样最大的饼就翻到了最上面。

2、用锅铲将前n块饼全部翻转，这样最大的饼就翻到了第n块，也就是最后一块。

以上两个流程理解之后，基本就可以写出解法了，不过题目要求我们写出具体的反转操作序列，这也很简单，只要在每次翻转烧饼时记录下来就行了。

二、代码实现

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

//记录反转操作序列LinkdListIntgrrs=nwLinkdList();ListIntgrpancakSort(int[]caks){sort(caks,caks.lngth);rturnrs;}voidsort(int[]caks,intn){//bascasif(n==1)rturn;//寻找最大饼的索引intmaxCak=0;intmaxCakIndx=0;for(inti=0;in;i++)if(caks[i]maxCak){maxCakIndx=i;maxCak=caks[i];}//第一次翻转，将最大饼翻到最上面rvrs(caks,0,maxCakIndx);rs.add(maxCakIndx+1);//第二次翻转，将最大饼翻到最下面rvrs(caks,0,n-1);rs.add(n);//递归调用sort(caks,n-1);}voidrvrs(int[]arr,inti,intj){whil(ij){inttmp=arr[i];arr[i]=arr[j];arr[j]=tmp;i++;j--;}}

通过刚才的详细解释，这段代码应该是很容易理解的。

算法的时间复杂度很容易计算，因为递归调用的次数是n，每次递归调用都需要一次for循环，时间复杂度是O(n)，所以总的复杂度是O(n^2)。

最后，可以思考一个问题：按照我们这个思路，得出的操作序列长度应该为2(n-1)，因为每次递归都要进行2次翻转并记录操作，总共有n层递归，但由于bascas直接返回结果，不进行翻转，所以最终的操作序列长度应该是固定的2(n-1)。

显然，这个结果不是最优的（最短的），比如说一堆煎饼[,2,4,1]，我们的算法得到的翻转序列是[,4,2,,1,2]，但是最快捷的翻转方法应该是[2,,4]：

初始状态：[,2,4,1]翻前2个：[2,,4,1]翻前个：[4,,2,1]翻前4个：[1,2,,4]

如果要求你的算法计算排序烧饼的最短操作序列，你该如何计算呢？或者说，解决这种求最优解法的问题，核心思路什么，一定会使用到什么算法技巧呢？

不妨分享一下你的思考。