燒餅排序

燒餅排序是個(gè)很有意思的實(shí)際問題：假設(shè)盤子上有 n 塊面積大小不一的燒餅，你如何用一把鍋鏟進(jìn)行若干次翻轉(zhuǎn)，讓這些燒餅的大小有序（小的在上，大的在下）？

設(shè)想一下用鍋鏟翻轉(zhuǎn)一堆燒餅的情景，其實(shí)是有一點(diǎn)限制的，我們每次只能將最上面的若干塊餅子翻轉(zhuǎn)：

我們的問題是，如何使用算法得到一個(gè)翻轉(zhuǎn)序列，使得燒餅堆變得有序？

首先，需要把這個(gè)問題抽象，用數(shù)組來表示燒餅堆：

一、思路分析

為什么說這個(gè)問題有遞歸性質(zhì)呢？比如說我們需要實(shí)現(xiàn)這樣一個(gè)函數(shù)：

// cakes 是一堆燒餅，函數(shù)會(huì)將前 n 個(gè)燒餅排序 void sort(int[] cakes, int n);

如果我們找到了前 n 個(gè)燒餅中最大的那個(gè)，然后設(shè)法將這個(gè)餅子翻轉(zhuǎn)到最底下：

那么，原問題的規(guī)模就可以減小，遞歸調(diào)用 pancakeSort(A, n-1) 即可：

接下來，對(duì)于上面的這 n - 1 塊餅，如何排序呢？還是先從中找到最大的一塊餅，然后把這塊餅放到底下，再遞歸調(diào)用 pancakeSort(A, n-1-1)……

你看，這就是遞歸性質(zhì)，總結(jié)一下思路就是：

1、找到 n 個(gè)餅中最大的那個(gè)。

2、把這個(gè)最大的餅移到最底下。

3、遞歸調(diào)用 pancakeSort(A, n - 1)。

base case：n == 1 時(shí)，排序 1 個(gè)餅時(shí)不需要翻轉(zhuǎn)。

那么，最后剩下個(gè)問題，如何設(shè)法將某塊燒餅翻到最后呢

其實(shí)很簡(jiǎn)單，比如第 3 塊餅是最大的，我們想把它換到最后，也就是換到第 n 塊。可以這樣操作：

1、用鍋鏟將前 3 塊餅翻轉(zhuǎn)一下，這樣最大的餅就翻到了最上面。

2、用鍋鏟將前 n 塊餅全部翻轉(zhuǎn)，這樣最大的餅就翻到了第 n 塊，也就是最后一塊。

以上兩個(gè)流程理解之后，基本就可以寫出解法了，不過題目要求我們寫出具體的反轉(zhuǎn)操作序列，這也很簡(jiǎn)單，只要在每次翻轉(zhuǎn)燒餅時(shí)記錄下來就行了。

二、代碼實(shí)現(xiàn)

只要把上述的思路用代碼實(shí)現(xiàn)即可，唯一需要注意的是，數(shù)組索引從 0 開始，而我們要返回的結(jié)果是從 1 開始算的。

// 記錄反轉(zhuǎn)操作序列 LinkedList<Integer> res = new LinkedList<>();List<Integer> pancakeSort(int[] cakes) {sort(cakes, cakes.length);return res; }void sort(int[] cakes, int n) {// base caseif (n == 1) return;// 尋找最大餅的索引int maxCake = 0;int maxCakeIndex = 0;for (int i = 0; i < n; i++)if (cakes[i] > maxCake) {maxCakeIndex = i;maxCake = cakes[i];}// 第一次翻轉(zhuǎn)，將最大餅翻到最上面reverse(cakes, 0, maxCakeIndex);res.add(maxCakeIndex + 1);// 第二次翻轉(zhuǎn)，將最大餅翻到最下面reverse(cakes, 0, n - 1);res.add(n);// 遞歸調(diào)用sort(cakes, n - 1); }void reverse(int[] arr, int i, int j) {while (i < j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;i++; j--;} }

算法的時(shí)間復(fù)雜度很容易計(jì)算，因?yàn)檫f歸調(diào)用的次數(shù)是 n，每次遞歸調(diào)用都需要一次 for 循環(huán)，時(shí)間復(fù)雜度是 $O(n)$，所以總的復(fù)雜度是 $O(n^2)$。

總結(jié)

以上是生活随笔為你收集整理的烧饼排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。