趣题：用最少的块移动实现逆序操作

原文

上次那篇日志发布之后，据说大家解题的热情相当高。Michael Brand告诉我说，他收到了很多来自中国的邮件，他感到非常高兴。在揭晓谜底之前，还是让我们先回顾一下题目：

    对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方（说穿了就是一次选择剪切粘贴的操作）。例如，数列1,4,5,6,2,3,7可以通过一次块移动完成排序（把456挪到3后面）。那么，想要让一个1到n的逆序排列n, n-1, ..., 3, 2, 1变为顺序排列，最少需要多少次块移动？给出你的算法，并证明这个移动数目不能再少了。
    需要指出的是，答案并不是n-1那么简单。当n=5时，只需要三步就可以搞定了：

5 4 [3 2] 1
3 2 5 [4 1]
[3 4] 1 2 5
1 2 3 4 5

    事实上，给出1到n的逆序排列，最少需要Ceil[(n+1)/2]次块移动就可以完成排序（除了n=1或n=2，Ceil表示取上整）。当n为奇数时，一个满足要求的算法是：每一次把数字n后面那一段的正中间两个元素拿出来，插入到数字n前面那一段数的正中间。当数字n后面的数被移动完了后，把它前面n-1个数左右两半对换一下就行了。例如，当n=7时：

7 6 5 [4 3] 2 1
4 3 7 6 [5 2] 1
4 5 2 3 7 [6 1]
[4 5 6] 1 2 3 7
1 2 3 4 5 6 7
    算法的移动步数显然为(n+1)/2，其正确性可以用数学归纳法说明，这里不再详细叙述了。
    当n为偶数时，只需要用n/2次操作把前面n-1个元素排好序，再花一次操作把末一个元素移动到最前面，加起来正好Ceil[(n+1)/2]次操作。下面我们证明，移动次数不可能比Ceil[(n+1)/2]更少。
    对于数列中相邻的两个数，如果前面那个数比后面的大，我们就把它们俩称作一组“逆序相邻数”。初始时，数列中有n-1个这样的逆序相邻数，我们的目标就是通过块移动把这个数目减少到0。整个证明过程的关键就在于，一次块移动操作最多只能消除两个逆序相邻数。

原数列： **aA--Bb***CD****
新数列： **ab***CA--BD****

    假如我们把块A--B插入到CD中间。注意到，相邻数发生变动的地方只有三处。要想同时消除三个逆序相邻数，只有一种可能：原数列中a>A, B>b, C>D，同时新数列中的a<b, C<A, B<D。这将导出一个很荒谬的结论：A < a < b < B < D < C < A。这告诉我们，一次块移动同时消除三个逆序相邻数是不可能的，它最多只能消除两个逆序相邻数。另外，容易看出，第一次移动只能消除一个逆序的相邻数，因为初始时原数列完全逆序，即有a > A > B > b > C > D，在新数列中只有C<A成立。对称地，最后一次移动也只可能消除一个逆序相邻数，因为新数列中a < b < C < A < B < D，只有B>b是成立的。
    于是我们得知，k次块移动最多消除1+2*(k-2)+1个逆序相邻数。为了消除n-1个逆序相邻数，我们有1+2*(k-2)+1 >= n-1，整理得k>=(n+1)/2。