烙饼排序 | Acm之家

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

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

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

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

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

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

Read full article from 烙饼排序 | Acm之家