【经典算法】:烙饼排序

桃扇骨 2022-07-21 01:27 143阅读 0赞

原理非常简单，看视频即可

给一个为排序的数组，你只能再改对该数组做如下操作：flip(arr, i): 将数组arr\[0...i\]进行逆置。如何对该数组进行排序？

这个问题在编程之美一书也有提及：

星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小次序摆好——小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到最后大小有序的结果呢？”

你能否写出一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程呢？

关于这个问题的最优化解法是比较困难的，大家可以参考书上的解法。

这里只给出直接的解法。算法思想类似选择排序，每次找到一个最大的元素，对其进行两次 flip操作，可将最大的放在最后面，让后缩小数组的范围。因此最大需要 2\*(n-1)次flip操作。

可以通过下面的视频理解这个操作过程：

C++代码实现如下：

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>#include &lt;stdlib.h&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>02</code></td> 
   <td><code>#include &lt;stdio.h&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>07</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>temp, start = 0;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>08</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(start &lt; i)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>10</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp = arr[start];</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>11</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>arr[start] = arr[i];</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>13</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>start++;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>18</code></td> 
   <td><code>/* 找出 arr[0..n-1] 内最大的元素的下标 */</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>19</code></td> 
   <td><code>int</code> <code> findMax(</code><code>int</code> <code> arr[], </code><code>int</code> <code> n)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>25</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>mi;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>28</code></td> 
   <td><code>int</code> <code> pancakeSort(</code><code>int</code> <code> *arr, </code><code>int</code> <code> n)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>30</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// 每次翻转可以定位一个做大的元素</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>33</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// 在 arr[0..curr_size-1] 找到最大的元素</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>34</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>mi = findMax(arr, curr_size);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>36</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//记性两次flip操作，将最大的元素翻转到最后</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>46</code></td> 
   <td><code>void</code> <code> printArray(</code><code>int</code> <code> arr[], </code><code>int</code> <code> n)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>49</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>printf</code><code>(</code><code>"%d "</code><code>, arr[i]);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>55</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>n = </code><code>sizeof</code><code>(arr)/</code><code>sizeof</code><code>(arr[0]);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>57</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>pancakeSort(arr, n);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>59</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>puts</code><code>(</code><code>"Sorted Array "</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>60</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>printArray(arr, n);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>62</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>0;</code></td> 
  </tr> 
 </tbody> 
</table>