趣题：用最少的“并行交换”完成排序

一道牛B题目被出成POJ的月赛题了。那道题目真的很好玩，题目和解答都很简单有趣。其实我挺喜欢这种“给出一个算法并证明该算法最优”类型的数学题目。这里再和大家分享一个类似的比较老的题目，有兴趣的话不妨先想想再看答案。

一次“交换”操作是指将数列中的两个数位置对换。我们假设，互不相交的若干个交换操作可以一次同时进行；换句话说，如果k个交换中任两个都不会对同一个数进行操作，那么这k个操作可以并行完成。例如，在数列

10, 6, 8, 5, 2, 3, 1, 4, 7, 9

中，我们可以同时交换第4个数和第6个数，第8个数和第9个数，以及第3个数和第7个数。经过这一次“并行交换”后，数列变为：

10, 6, 1, 3, 2, 5, 8, 7, 4, 9

任意给定一个长度为n的全排列，请问对该序列进行排序最坏情况下需要多少次并行交换？给出一种具体的算法，说明这个次数足够了；并且给出一种最坏情况，证明这个次数是必需的。

这种“并行交换”是如此的强大，以致于我们要问自己的第一个问题是，是否有可能对所有数列都只需要一次并行交换就够了。不难发现，除了n=1和n=2之外，对于其它的n，我们总能找到一个数列，它至少需要两次并行交换才能完成排序。考虑到一次并行交换只能变动偶数个数的位置，因此我们只需要弄出一个有奇数个数不在正确位置上的排列就可以了。对于n≥3的情况，这总是可以办到的，例如数列2, 3, 1, 4, 5, 6, 7, …, n（仅让最前面的1、2、3三个数位置顺次挪一位）就可以了。这样的话，我们要不然就无法处理完所有要移动的数，要不然就会动到已经在目标位置上的数，总之一次交换是怎么也不能满足要求。

令人吃惊的是，不管n有多大，不管数列有多乱，最多只需要2次并行交换就可以排好序了。为了证明这一点，我们首先看一种特殊情况：对于“顺次挪动一位”，即“2占了1该在的位置，3又占了2应该在的位置，……，n占了n-1的位置，最后1又占了n本该在的位置”的情况，如何用两次并行交换调整顺序。回想一下线性时间常数附加空间的数组循环移动的算法，我们立即得到了我们需要的算法：由于循环移动一位相当于两次逆序操作，而一次逆序操作可以由前后对称位置上的n/2组交换完成，因此我们只需要两次并行交换即可。具体地说，对于下面这个数列

2, 3, 4, …, n-1, n, 1

首先将整个序列进行逆序，即2和1交换，3和n交换，4和n-1交换，……，于是得到：

1, n, n-1, …, 4, 3, 2

接下来，将得到的序列的后面n-1位再逆序一次，即n和2交换，n-1和3交换，……，于是数列就变成了

1, 2, 3, 4, …, n-1, n

这样，我们就可以只用两次并行交换完成“循环移动一位”型的数列了。

到这里，我们离最终的答案已经很近很近了。最关键的一点是，这个“循环移动一位”可以是广义的。换句话说，只要是“数字1应该到现在4的位置上去，而4又该移到7的位置上去，7则本该在现在2的位置上，而2又该替代现在的1”一类的“圈”，我们都可以用上面的方法在两步以内还原为应有的顺序。一旦想到了任何一个排列总能分解成若干个互不相交的循环时，我们的问题也就立即解决了。

举个例子，我们对原题中的例子

10, 6, 8, 5, 2, 3, 1, 4, 7, 9

进行排序。这个数列包含了两个循环：10 -> 9 -> 7 -> 1 -> 10，以及6 -> 3 -> 8 -> 4 -> 5 -> 2 -> 6。也就是说，我们要把[10,9,7,1]四个数依次变成[1,10,9,7]，同时把[6,3,8,4,5,2]变成[2,6,3,8,4,5]。在第一步，我们把第一个循环中的(10,1)和(9,7)进行交换以实现逆序，同时并行地在另一个不相交的循环中进行同样的操作，将(6,2)、(3,5)和(8,4)进行交换；第二步，我们把每个循环中的后面一段进行逆序，即交换第一个循环中的(10,7)，同时交换第二个循环中的(6,5)和(3,4)。

10, 6, 8, 5, 2, 3, 1, 4, 7, 9<--- 初始 1, 2, 4, 3, 6, 5 10, 8, 9, 7<--- 第一步后 1, 2, 3, 4, 5, 6, 7, 8, 9 10<--- 第二步后 用这种方法，任何一个序列都可以在两步以内排好序。 题目来源：http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/April1999.html