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

当我们研究复杂度时，我们往往会将现实机器进行理想化。例如，我们说冒泡排序是O(n^2)的，这其实是不准确的。这个论断假设整数之间的比较运算是O(1)的，而事实上它们是O(log(min(|a|,|b|)))的。多数时候我们都认为这种机器模型的理想化是合理的，毕竟这让问题简化了不少，并且也能反映出算法的本质。但大家有想过吗，这个“大整数随便算”的假设其实是一个超级大漏洞，我们可以利用理想模型中的这一漏洞来作弊，获得时间复杂度更低的算法。上个月，Michael Brand在他的UyHiP（www.brand.site.co.il/riddles/）里就提出了这样一个问题（www.brand.site.co.il/riddles/200812q.html）：假设计算机对任意大整数的赋值、四则运算、取余运算、比较运算、位运算（包括左移右移）的复杂度都是常数级别，你能否设计出一个O(n)的排序算法来？

我非常喜欢这个题目。月初的时候我就提交了一个正确的算法。我们将用左移和加法运算把整数序列编码成一个超大整数，然后利用排序网络进行并行排序。这个算法比较复杂，你可以按照下面的思路一步一步得到这个算法。

1. 如何用位运算来取绝对值？

2. 给出两个正整数a, b，不用比较运算和判断语句如何把小数赋给a，大数赋给b？

提示：和加差除以2等于大数，和减差除以2等于小数

3. 如何利用位运算把整数序列编码成一个超大整数？

例如把（二进制数）11, 1011, 1110, 1编码为一个数00011 01011 01110 00001

4. 如何用位运算给超大整数中的所有数同时取绝对值？

5. 给出两个超大整数a, b，不用比较运算和判断语句如何把对应位置上的小数赋给a的对应位置，大数赋给b的对应位置？ 例如把

a = 000010 000111 000100 001001

b = 000001 001011 000011 011111

变成

a = 000001 000111 000011 001001

b = 000010 001011 000100 011111

6. 如何实现奇偶移项排序？

最后，由于奇偶移项排序只有O(n)层，因此整个算法是O(n)的。

但是，这个算法太繁琐了，不具有美观性。虽然这个算法是我自己想出来的，但我仍然很不满意。待我看了这个月Michael Brand发布的答案后，我一拍大腿，哎呀，还有一个如此简单巧妙的算法我没想到！相比之下，我的算法太复杂了，原因就在于我还没有充分挖掘到“大整数的常数级运算”的潜力。这个理想模型的假设太强大了。打开思路，放宽思维，大胆想象，从更大的尺度上来思考，我们可以得到一个简单得出奇的线性排序算法来。

这个理想模型牛B就牛B在，我可以用大整数实现任意长度的数组的常数级别存取！比如，我们假设数组a的“单位宽度”为w，那么让a[i]自加一就相当于让一个超大二进制整数a加上1<<(i*w)。想要取出a[i]的值，也就相当于让a>>(i*w)再模1<<w。再回想位运算的一个妙用：x and (x xor (x-1))，或者写成x and -x，可以取出（二进制数）x的最右边那个1。此时，问题立刻迎刃而解。维护一个超级超级长的二进制数a，再维护一个超级超级长的数组b。只要读到一个数x，如果b[1<<x]为0，我们就让a加上1<<x。然后，令b[1<<x]自加一。输出时，只需要不断取a中位置最低的那个“1”，然后按照b数组的值输出相应多个数即可。一个问题是，我们这样输出的是1<<x啊，要想输出原来的数x该咋办？是不是还要想办法用常数时间实现log运算呢？哈哈，你又想复杂了！只需要再维护一个数组c，每次读到x时，令c[1<<x]=x即可。到时候呢，直接输出c数组里面的值就可以了。因此，整个算法流程如下：

for (i=0; i<n; i++)
{
    read(x);
    a = a | (1<<x);
    b[1<<x]++;
    c[1<<x] = x;
}
 
while (a > 0)
{
    x = a & (-a);
    for (i=0; i<b[x]; i++) output(c[x]);
    a = a - x;
}

其中，b的“单位宽度”为n的长度，c的“单位宽度”为数据中最大数的长度。这两个数组本身都能用超大整数直接实现。

另一个问题是，要是输入数据中有负数该咋办？也很简单，只需要在初始时把每个数都加上一个充分大的数，排序完成后再减掉它就行了。