最簡單的排序算法

陳凱

在一次電視節(jié)目上，谷歌總裁施密特提出問題：“如何才能更有效地對一百萬個32位長整數(shù)進行排序？”同在現(xiàn)場的奧巴馬立刻響應(yīng)道：“肯定不能用冒泡排序法?！笔┟芴卦u價說：“天哪！他是從誰那里聽說這個的?！?/p>

冒泡排序很簡單，其原理也比較容易理解，但冒泡排序效率很差。世上也存在著許多效率很高的排序算法，但它們又都比較難理解。本文將介紹一種簡單又“高效”的排序算法——珠排序，大家不妨一起來玩玩。

空間站里玩排序

之所以要在“高效”兩個字上打引號，是因為珠排序需要特殊的硬件支持。怎么個特殊法呢？為了方便說明問題，請想象在某個失重的空間站里，有一系列排列整齊、從1到n依次編了號碼的透明管子，在管子里放入小球，小球的直徑與管子橫截面的直徑相仿，只是略小一點，放球的規(guī)則如下：

①預(yù)先設(shè)定一系列未排序的數(shù)字，如5、4、8、1、2、3、6、4。

②按預(yù)先設(shè)定的數(shù)字往管子里放球，如果是5，就放5個球，但并不是把5個球都放到1個管子中，而是依次放入1號到5號管子。如果是4，就把4個球依次放入1號到4號管子（如圖1A、B）。

③在空間站的無引力真空環(huán)境中，所有球都浮在空中，這時候若忽然施加重力，如用離心力模擬重力，于是所有的球都掉到了管子的底部，這時如果從側(cè)面數(shù)球的個數(shù)，就能發(fā)現(xiàn)，先前的未排序數(shù)字，此時已經(jīng)排序完成了（如圖1C、D）。

這個實驗當然不一定非要在太空站里做，把原本水平放置的管子豎立起來，產(chǎn)生的效果也是一樣的。

記事本里玩排序

即便沒有管子和小球，也可以在記事本中模擬珠排序的過程。

假設(shè)預(yù)設(shè)的未排序的數(shù)字為5、4、8、1、2、3、6、4，第一個數(shù)字是5，則在記事本的第一列（注意是列而不是行）寫5個“1”，然后再在“1”下面多補充一些“0”，因為需要排列的數(shù)字最大是8，用8減去5得3，則最少補充3個“0”，當然多補充點“0”是沒關(guān)系的，接著要排序的數(shù)字是4，則在記事本第二列寫4個“1”，再補充4個“0”，第三列8個“1”……以此類推（如圖2）。

把所有的1和0按次序排列好后，用記事本中的“編輯—替換”功能，將文本中的“10”全部替換成“01”，反復(fù)這個全部替換過程，當不再有可替換的對象時，排序也就完成了（如圖3）。就這樣，不用寫一行代碼就完成了排序。當然，若想要一本正經(jīng)地把珠排序的代碼寫出來，也不是特別困難的事情，這個任務(wù)就交給有興趣的朋友自行探索了。

反復(fù)點“全部替換”按鈕，最后替換就完成了，每一列的“1”的個數(shù)是1、2、3、4、4、5、6、8，正是5、4、8、1、2、3、6、4排序后的結(jié)果（如圖4）。