最簡(jiǎn)單的排序算法

陳凱

在一次電視節(jié)目上，谷歌總裁施密特提出問(wèn)題：“如何才能更有效地對(duì)一百萬(wàn)個(gè)32位長(zhǎng)整數(shù)進(jìn)行排序？”同在現(xiàn)場(chǎng)的奧巴馬立刻響應(yīng)道：“肯定不能用冒泡排序法。”施密特評(píng)價(jià)說(shuō)：“天哪！他是從誰(shuí)那里聽(tīng)說(shuō)這個(gè)的。”

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

空間站里玩排序

之所以要在“高效”兩個(gè)字上打引號(hào)，是因?yàn)橹榕判蛐枰厥獾挠布С帧Ｔ趺磦€(gè)特殊法呢？為了方便說(shuō)明問(wèn)題，請(qǐng)想象在某個(gè)失重的空間站里，有一系列排列整齊、從1到n依次編了號(hào)碼的透明管子，在管子里放入小球，小球的直徑與管子橫截面的直徑相仿，只是略小一點(diǎn)，放球的規(guī)則如下：

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

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

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

這個(gè)實(shí)驗(yàn)當(dāng)然不一定非要在太空站里做，把原本水平放置的管子豎立起來(lái)，產(chǎn)生的效果也是一樣的。

記事本里玩排序

即便沒(méi)有管子和小球，也可以在記事本中模擬珠排序的過(guò)程。

假設(shè)預(yù)設(shè)的未排序的數(shù)字為5、4、8、1、2、3、6、4，第一個(gè)數(shù)字是5，則在記事本的第一列（注意是列而不是行）寫(xiě)5個(gè)“1”，然后再在“1”下面多補(bǔ)充一些“0”，因?yàn)樾枰帕械臄?shù)字最大是8，用8減去5得3，則最少補(bǔ)充3個(gè)“0”，當(dāng)然多補(bǔ)充點(diǎn)“0”是沒(méi)關(guān)系的，接著要排序的數(shù)字是4，則在記事本第二列寫(xiě)4個(gè)“1”，再補(bǔ)充4個(gè)“0”，第三列8個(gè)“1”……以此類(lèi)推（如圖2）。

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

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