趣题：理想模型下的排序算法（下）

上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted（www.brand.site.co.il/riddles/200901a.html），在这里向Michael Brand表示深深的膜拜。

自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。

为了能够实现常数时间的排序，我们首先应该想想，怎样才能“一下子”比较出所有数两两之间的大小。想到我们的整数串可以要有多大就有多大，我们萌生了一个大胆的想法：把本来就装了n个数的整数串继续扩展，让每个整数串里面都扩展到n^2个数，为n^2对数的比较做好准备。我们希望有一个操作能够让0100 0111 0001 0010变成下面两个更大的整数串；

0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010…. (大整数串A)

0100 0100 0100 0100 0111 0111 0111 0111 0001 0001 0001 0001 0010 0010 0010 0010…. (大整数串B)

这为以后并行比较n^2个数对创造了条件。大整数串A很好构造，让0100 0111 0001 0010乘以

0000 0000 0000 0001 0000 0000 0000 0001 0000 0000 0000 0001 0000 0000 0000 0001…. (基本掩码)

即可。上面这个数又是怎么在常数时间内生成的呢？很简单，只需要用64个1除以16个1即可，正如十进制中999999/99 = 010101一样。而连续的1又可以通过左移后减一得到，因此整个数可以在常数时间内算出。我们把这样的串叫做“基本掩码”，以后将多次用到。

难就难在大整数串B。大整数串B又可以看作是

0000 0000 0000 0100 0000 0000 0000 0111 0000 0000 0000 0001 0000 0000 0000 0010…. (1)

乘以0001 0001 0001 0001得到的结果。后面这个0001 0001 0001 0001的生成办法和前面一样，关键是前面这个等价于“加大定宽”的操作(1)该怎么做。我当初思考这个问题时就卡在这一步了。Michael Brand就是牛，他想到了这关键性的一步：要是“定宽”再大一点就好了。如果需要生成的大整数串是

0000 0000 0000 0000 0100 0000 0000 0000 0000 0111 0000 0000 0000 0000 0001 0000 0000 0000 0000 0010…. (2)

的话就好办了，只需要把大整数串A

0000 0000 0000 0000 0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010

与

0000 0000 0000 0000 1111 0000 0000 0000 0000 1111 0000 0000 0000 0000 1111 0000 0000 0000 0000 1111…. (3)

进行and运算即可。上面的序列(3)可由基本掩码乘以1111获得。我们甚至可以实现“缩小定宽”的操作，只要新定宽和原定宽相差足够多（具体的说，新定宽×数的个数≤原定宽）。把(2)式对1111 1111 1111 1111取模，我们就可以重新得到0100 0111 0001 0010（这个取余操作相当于把原来的64位数截成4个16位数后求和，正如十进制中23000067 mod 9999 = 2367 = 2300 + 0067一样）。

有了“定宽扩展到充分大”和“定宽缩小到充分小”的操作，我们立即得到了大整数B的常数时间生成方法：先把原始整数串0100 0111 0001 0010的定宽加到足够大，然后再缩小到原定宽的n倍（例子中为4×4=16）。这两个操作都是常数级别的，因此总的操作也是常数级别的。乘以0001 0001 0001 0001后，我们就得到了大整数串B。

接下来，我们着手构造比较函数。我们希望能够同时比较两个整数串对应的16个数，并且返回新的大整数串来表明每一对数中哪个大哪个小。我们比较时采用的基本方法就是，如果a比b小，那么~a+b一定会越界。考虑一个中间情况就是，如果a=b话，~a+b正好就等于111…11，是该定宽下所能表示的最大数。如果a的值减小一些，~a的值就会增大一些，~a+b就溢出了；反之，如果a的值变大一些，~a的值反而会减小，~a+b就应该小于该定宽下的最大数。熟悉补码的朋友可能想到，这是受到了计算机做减法的办法的启发。为了能够让大整数串顺利接受溢出并返回结果，在最初取定宽时应该让定宽大小比最大数位数还多一位（相当于符号位）。即使当初没想到这一点，把整数串排的紧紧的，现在后悔也来得及——我们已经有了常数时间修改定宽的办法。整个大整数串取反后，我们用一个and运算把多出来的符号位归零。相加后再用and运算把符号位提取出来，通过右移获得比较结果。

0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010…. (大整数串A)

0100 0100 0100 0100 0111 0111 0111 0111 0001 0001 0001 0001 0010 0010 0010 0010…. (大整数串B)

1011 1011 1011 1011 1000 1000 1000 1000 1110 1110 1110 1110 1101 1101 1101 1101…. (大整数串B取反)

0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111…. (掩码，可在常数时间里生成)

0011 0011 0011 0011 0000 0000 0000 0000 0110 0110 0110 0110 0101 0101 0101 0101…. (上面两序列and后的结果)

0111 1010 0100 0101 0100 0111 0001 0010 1010 1101 0111 1000 1001 1100 0110 0111…. (大整数串A与上一序列相加)

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000…. (掩码，可在常数时间里生成)

0000 1000 0000 0000 0000 0000 0000 0000 1000 1000 0000 1000 1000 1000 0000 0000…. (上面两序列and后的结果)

0000 0001 0000 0000 0000 0000 0000 0000 0001 0001 0000 0001 0001 0001 0000 0000…. (上一序列右移3位)

最后这个整数串中只有0和1两个数，1表示对应位置上B串的数比A串的小，0的意义则正好相反。如果最初读入的n个数没有重复的话，这里面应该恰好有n(n-1)/2个数字1（本例中则是6个）。

到这里，我们已经看到胜利的希望了。如果您真能一个字一个字的读到这里来，我向您表示深深的崇敬和膜拜。剩下的事情已经不多了，主要是统计和还原两个操作。

我们得到了一个表示出16个大小关系的整数串，现在我们想把它们合并回去，算出对于每一个给定的数，有多少个数比它小。换句话说，我们希望将比较结果中的每第四个数加起来，得到0010 0011 0000 0001，其中0010就是0000、0000、0001、0001四个数相加的结果，它表示输入数据中有两个数比输入的第一个数0100小，类似地其余的数也是由对应的四个值相加得到。实现这一点并不困难，只需要让比较结果对1111 1111 1111 1111取模即可，其原理与前面的缩小定宽操作是相同的。我们把这个序列叫做索引序列。

最后一个步骤便是按照索引0010 0011 0000 0001将0100 0111 0001 0010重新排列，使得Input[i] = Result[Index[i]]。这一步又是一大难关，我想即使我当初想到了改变定宽的方法，最终也会卡在这最后一步。为了实现顺序排列，我们需要强行建立一个有序索引。我们希望在常数时间内得到“计数序列”0000 0001 0010 0011，它将用于进一步的操作。计数序列的生成并不难，要想生成一个有n项的定宽为w的计数序列，我们仅仅需要找出一个等价于

0·2^(w(n-1)) + 1·2^(w(n-2)) + 2·2^(w(n-3)) + … + (n-1)·2^0

的公式来就行了。我们不用把时间浪费在寻找公式上，用Mathematica就可以得到我们想要的结果。从下图中可以看到一个好消息：公式是O(1)的，其复杂度不随变量增大而增大，并且所有计算都可以在O(1)的时间内完成。稍作验证可知，这个公式是正确的。

接下来我们要做的是，将索引序列与计数序列进行比较，比较的方法将再次套用上述从生成大整数串到并行比较n^2个数对的所有步骤。

0000 0000 0000 0000 0001 0001 0001 0001 0010 0010 0010 0010 0011 0011 0011 0011…. (扩展的计数序列)

0010 0011 0000 0001 0010 0011 0000 0001 0010 0011 0000 0001 0010 0011 0000 0001…. (扩展的索引序列)

0001 0001 0000 0001 0001 0001 0000 0000 0000 0001 0000 0000 0000 0000 0000 0000…. (对应位置上计数序列较小)

0000 0000 0000 0000 0000 0000 0001 0000 0000 0000 0001 0001 0001 0000 0001 0001…. (对应位置上索引序列较小)

同样地，上面两个比较结果中数字1各有6个，一共12个。另外还有4个位置，你也不比我小，我也不比你小，两次比较的结果都是“0”。显然，这4个位置所对应的数从左至右分别是前4个自然数。用or运算和xor运算提取出这四个位置，然后与最初的大整数串B进行and运算：

0001 0001 0000 0001 0001 0001 0001 0000 0000 0001 0001 0001 0001 0000 0001 0001…. (上述两比较结果的or运算)

0000 0000 0001 0000 0000 0000 0000 0001 0001 0000 0000 0000 0000 0001 0000 0000…. (上一序列与基本掩码进行异或)

0000 0000 1111 0000 0000 0000 0000 1111 1111 0000 0000 0000 0000 1111 0000 0000…. (上一序列乘以1111)

0100 0100 0100 0100 0111 0111 0111 0111 0001 0001 0001 0001 0010 0010 0010 0010…. (大整数串B)

0000 0000 0100 0000 0000 0000 0000 0111 0001 0000 0000 0000 0000 0010 0000 0000…. (上面两个序列and后的结果)

最后这个序列满足这样的性质：数的出现顺序和输入数据相同，并且当你把它从左至右划分为n个n元组之后，输入数据中第i小的数恰好在它所在的n元组中的第i个位置。和上面一样，我们需要把每第四个元素合并在一起。将最后这个结果模1111 1111 1111 1111后，即得到0001 0010 0100 0111。这样，我们就在常数时间里完成了n个数的排序。

嗯，你真强大，竟然一路看到这里来了。不知道大伙儿看明白没，麻烦大家在下面留句话。或许大家会想，O(1)的排序算法……总算不能再牛B了吧？呵呵，你又错了，我们现在所看到的仍然太表层，真正牛B的还远没有挖掘出来呢！接下来，我们还会利用大整数的理想运算做一些更加牛B的事情。