Author: Fox
首先声明：本人没有解决掉这个问题。
相比第一道让CPU占用率曲线听你指挥对Windows系统中CPU占有率概念的考察和对API的使用，以及第二道中国象棋将帅问题对抽象建模的考察。这道题目才算是一道算法题吧？之前那两道尤其是中国象棋将帅问题总有点脑筋急转弯的味道。
题目：星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：
“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小次序摆好——小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。
我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到最后大小有序的结果呢？
你能否写出一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程呢？
排序问题是数据结构和算法中比较重要的一个了，之前在一篇被同事成为标题党的文章中因为提到排序中关于（非）稳定排序的概念还被很多TX鄙视了一番，甚至引来人身攻击，现在想来都有些后怕。
这道题目一眼看上去最先让我想到的居然是那道经典的汉诺塔（Tower of Hanoi）问题（当然，汉诺塔不算排序问题）。
1) 相似点★：
a. 都要不断调整位置，最终实现从小到大排好；
b. 都要借助中间量进行调整。
2) 不同处★：
a. 汉诺塔有多出来的两根针，翻烙饼只有一只手，明确说明没有第三只手；
b. 汉诺塔一次只能移动一个，翻烙饼没限制；
c. 汉诺塔要保证小的始终在上面，翻烙饼没限制；
d. 汉诺塔移动之前就有序，所以其移动次数是固定的，算法的逻辑也固定（不管是递归还是栈操作），翻烙饼没有这个前提。
3) 把题目用程序语言描述一下吧★：
a. Input : n.
b. Process : generate n random number 0-(n-1), sortting.
c. Output : 0, 1, ..., n-1, and move times num.
4) 存储结构★★★：
我最开始想到的是：这一摞烙饼其实就是一个双链表，每翻一次相当于将头节点H与某非头节点N进行如下变换：
H->next = N->next
N->prior = H->prior = NULL
N->next->prior = H
如果使用普通的双链表，这儿就有一个很明显的问题，H和N之间的所有节点（如果有的话）的前趋prior和后继next互换了，对于n比较大的情况，这个操作明显浪费时间啊（交换前趋prior和后继next和题目要求的翻几次似乎也没有关系吧？只是我作为一个一线的Coder考虑的太具体了）。如果摒弃前趋和后继的概念，又该怎样描述呢？
唐朝禅宗大师青原行思曾说：参禅之初，看山是山，看水是水；禅有悟时，看山不是山，看水不是水；禅中彻悟，看山仍然山，看水仍然是水。
俗：日，扯那么多，什么意思？
师：前趋不是前趋，后继不是后继。
俗：日，前趋不是前趋，难道是后继吗？
师：然也。
Fox：O, my God！整点实际的吧！翻转一次之后，前趋视为后继，后继视为前趋，第奇数次翻转的前趋是后继，第偶数次翻转的后继是前趋。
整个链表的形态如下：
H:Head, F:First, G:F's next, B:C's prior, C:Change, D, C's next, L:Last.
H<==>F<==>G<=...=>B<==>C<==>D<=...=>L
F与C交换的操作如下（Word、PS画图），n表示next，p表示prior：
这里只需要修改F、D节点的prior，H、C节点的next，其他节点不变。
后面想了一下，这种方式很难在不添加flag或者对换n、p的情况下正常操作，没有找到好的方法L，如果你有好的方法不妨告诉我。
最后只好作罢，何苦呢？直接使用数组就完了嘛J！既然是数组，除了翻转移动麻烦一点，理解和操作还是很容易的。
果然不是搞数学、算法出身的，一上来考虑的就是如何存储^.^''''，而不是算法本身。
更可笑的是，扯了半天，最后居然还是用数组！
5) 算法分析★★★★★：
冒泡排序思想：
最关键的是要抽象出随机数列特征（含当前和移动后数列特征的抽象），并尽量使每一次翻转有效（所谓有效，即尽量保证每一次操作都向最后的有序靠近而非背离 ）。
师：要使大头在后，应使大头在后。
俗：日，这是什么狗屁逻辑？
师：因果。在前既是在后。
俗：USA, CNN（操你娘）。
师：翻转。既不在前，也不在后，使之在前，使之在后。
俗：日，什么东西？既不在前，也不在后，不前不后，难道在中间啊？
师：然也。
Fox：O, my God！整点实际的吧！整个过程分为n轮，在第i(i=0, 1, ..., n-1)轮：
a. 找到大头n-i，是否有序？是，转g；
b. 是否大头在后？是，转f；
c. 是否大头在前？是，转e；
d. 将队头（第一个元素）与大头n-i对调（别忘了是翻转，中间元素也变序了），++times；
e. 将队头n-i与第n-i个元素对调，++times；
f. ++i，转a；
g. 输出序列（0, 1, ..., n）和翻转次数times；OVER:D。
快速排序思想：
在最开始的时候，我就想到使用快速排序的思想，先使整个数列局部有序，最后调整使全部有序。悲哀的是，在我考虑 4 3 1 2这个数列的时候，我断定还要通过上面的方式重新像冒泡排序一样重新来过，立即放弃想法，于是给了上面的思路，而且坚定的认为这个方法已经很好。结果，下午GR告诉我他的反例：4 3 1 2 --> 2 1 3 4|--> 1 2| 3 4，“|”表示从该处翻转。
我必须承认，这才是好的方法，我过分拘泥于不去改动已经有序的部分。然而，这家伙只知道反驳我，却无法给出算法。
我只好自己重新考虑局部有序之后的问题。
十分钟后，我有了如下的答案（目前我能想到的最佳答案），但不得不承认，表述算法比给出一种情况对应的解要麻烦的多的多的多，假定A、B满足A==B-1，即A、B为相邻数列（为简单记，元素和数列统称数列）。则A、B的组合类型有8种：B(O)A(O)、B(C)A(O)、B(O)A(C)、B(C)A(C)、A(C)B(O)、A(O)B(O)、A(C)B(C)、A(O)B(C)，O表示正向（obverse）C表示逆向（reverse），以1 2 3 4为例：
B(O)A(O)：3 4 1 2<2>、B(C)A(O)：4 3 1 2<4>、B(O)A(C)：3 4 2 1<5>、B(C)A(C)：4 3 2 1<7>；
A(C)B(C)：2 1 4 3<1>、A(O)B(C)：1 2 4 3<3>、A(C)B(O)：2 1 3 4<6>、A(O)B(O)：1 2 3 4<8>。
对应操作规则如下：
a. 0x0101: B(O)A(O) --> B(C)A(O)； 3
b. 0x0001: B(C)A(O) --> A(C)B(O)； 2
c. 0x0101: B(O)A(C) --> B(C)A(C)；1
d. 0x0000: B(C)A(C)：如果当前只剩A、B两个子列，则翻转一次成A(O)B(O)1 2 3 4为最终结果，否则，认为B(C)A(C)可以作为一个逆序有序数列考虑，暂时无需翻转；
e. 0x1010: A(C)B(C) --> A(O)B(C)； 3
f. 0x1110: A(O)B(C) --> B(O)A(C)； 2
g. 0x1011: A(C)B(O) --> A(O)B(O)；1
h. 0x1111: A(O)B(O)：A、B可以作为一个有序数列考虑，如果当前只有A、B两个子列，则正序序列A(O)B(O)1 2 3 4为最终结果。
上面规则的制定其实是反向导出的，遵循的原则是，正序有序的A(O)B(O)和逆序有序的B(C)A(C)可以看作一个序列，A(C)B(O)、B(O)A(C)可一步达到，B(C)A(O)、A(O)B(C)可两步达到，B(O)A(O)、A(C)B(C)可三步达到。即对于4个元素，最坏的的A(C)B(C)需要4步（对应于上面的冒泡法却只需要3步L）。而且当元素比较多的时候，记住1、2个有序子列是可行的，但对于完全无序的数列，分析出所有有序子列，既不现实，也无必要。
修改规则如下：当队头无序&&相邻数列有序||队头有序，翻转队头；否则，将队头连同该元素一同翻转。
由此可见，这算法还要改进：
a. 判断Array[0]是否正序连续（连续个数nNum1），如果nNum1==n，转i，如果nNum1!=1，转c；
b. 判断Array[0]是否逆序连续（连续个数nNum1），如果nNum1==n，翻转Array，转f；
c. 从下标nNum1开始查找Array[0]+1（bObserve = true）和Array[0]-1（bObserve = false）的下标nStart2，如果nNum1==nStart2，bOrder1==true，转e，如果nNum1!=1，置nEnd2=nStart2；
d. 判断( bObserve == true&&Array[nStart2]+1==Array[nStart2+1] ) || ( bObserve == false&&Array[nStart2]==Array[nStart2+1]+1 )，true则置nEnd2=nStart2，false则置nEnd2=nStart2+1；
e. 翻转Array[0] to Array[nEnd2]，转a；
f. 输出Array及times。
这样来看，改进后的算法竟简单了许多！
不幸的是：按上面给出的算法翻转合并1 3 5 6 4 8 7 9 2 0：
1 3 5 6 4 8 7 9| 2| 0
2 9 7 8 4 6 5| 3| 1 0
3 5 6| 4| 8 7 9 2 1 0
4 6| 5| 3 8 7 9 2 1 0
5 6| 4 3 8 7 9 2 1 0
6 5 4 3 8| 7| 9 2 1 0
7 8 3 4 5| 6| 9 2 1 0
进入死循环了……
很明显应该是下面这个样子：
1 3 5 6 4 8 7 9 2| 0
9 8 7 4 6 5| 3 1 2 0
5 6 4| 7 8 9 3 1 2 0
6 5 4 7| 8 9 3 1 2 0
4 5 6 7 8 9 3| 1 2 0
3 4 5 6 7 8 9 1 2| 0
1 9 8 7 6 5 4 3 2| 0
2 3 4 5 6 7 8 9 1| 0
9 8 7 6 5 4 3 2 1 0|
0 1 2 3 4 5 6 7 8 9
执行9次翻转。算法如何得到呢？
a. 确定最小无序完整子集Sn（Sn中含n>1个连续数）；
b. 将Sn最前面的有序子集So（o>1）加以考虑，一个子集？两个子集？
______________________________________________________________________________
O, my God!
这个问题，从前天晚上到现在，思考、分析、抽象了至少有15个小时以上了：
a. Apr.18th-19th: 23:00 - 01:30
b. Apr.19th: 11:00 - 13:00
c. Apr.19th-20th: 22:00 - 05:30
d. Apr.20th: 11:00 - 15:00
结果是，到现在无法给出一个最优的翻转算法。一个周末都花在这上面了，准备放弃L。
LP催着我让我回学校，是该回去了！