最简单的排序算法

陈凯

在一次电视节目上，谷歌总裁施密特提出问题：“如何才能更有效地对一百万个32位长整数进行排序？”同在现场的奥巴马立刻响应道：“肯定不能用冒泡排序法。”施密特评价说：“天哪！他是从谁那里听说这个的。”

冒泡排序很简单，其原理也比较容易理解，但冒泡排序效率很差。世上也存在着许多效率很高的排序算法，但它们又都比较难理解。本文将介绍一种简单又“高效”的排序算法——珠排序，大家不妨一起来玩玩。

空间站里玩排序

之所以要在“高效”两个字上打引号，是因为珠排序需要特殊的硬件支持。怎么个特殊法呢？为了方便说明问题，请想象在某个失重的空间站里，有一系列排列整齐、从1到n依次编了号码的透明管子，在管子里放入小球，小球的直径与管子横截面的直径相仿，只是略小一点，放球的规则如下：

①预先设定一系列未排序的数字，如5、4、8、1、2、3、6、4。

②按预先设定的数字往管子里放球，如果是5，就放5个球，但并不是把5个球都放到1个管子中，而是依次放入1号到5号管子。如果是4，就把4个球依次放入1号到4号管子（如图1A、B）。

③在空间站的无引力真空环境中，所有球都浮在空中，这时候若忽然施加重力，如用离心力模拟重力，于是所有的球都掉到了管子的底部，这时如果从侧面数球的个数，就能发现，先前的未排序数字，此时已经排序完成了（如图1C、D）。

这个实验当然不一定非要在太空站里做，把原本水平放置的管子竖立起来，产生的效果也是一样的。

记事本里玩排序

即便没有管子和小球，也可以在记事本中模拟珠排序的过程。

假设预设的未排序的数字为5、4、8、1、2、3、6、4，第一个数字是5，则在记事本的第一列（注意是列而不是行）写5个“1”，然后再在“1”下面多补充一些“0”，因为需要排列的数字最大是8，用8减去5得3，则最少补充3个“0”，当然多补充点“0”是没关系的，接着要排序的数字是4，则在记事本第二列写4个“1”，再补充4个“0”，第三列8个“1”……以此类推（如图2）。

把所有的1和0按次序排列好后，用记事本中的“编辑—替换”功能，将文本中的“10”全部替换成“01”，反复这个全部替换过程，当不再有可替换的对象时，排序也就完成了（如图3）。就这样，不用写一行代码就完成了排序。当然，若想要一本正经地把珠排序的代码写出来，也不是特别困难的事情，这个任务就交给有兴趣的朋友自行探索了。

反复点“全部替换”按钮，最后替换就完成了，每一列的“1”的个数是1、2、3、4、4、5、6、8，正是5、4、8、1、2、3、6、4排序后的结果（如图4）。