趣味數(shù)學(xué)——桶排序

陳新龍

我們已經(jīng)講過(guò)多種排序的算法，都是利用不同的數(shù)學(xué)方法對(duì)數(shù)組列表進(jìn)行排序，比如冒泡排序、選擇排序……今天分享的排序算法名為桶排序，是數(shù)據(jù)結(jié)構(gòu)算法中一種簡(jiǎn)單高效并且容易理解的算法。

猴媽媽帶著5只小猴子去森林里摘香蕉，5只小猴子分別摘了5、2、5、3、7串香蕉。猴媽媽想看看自己孩子們摘香蕉的成果，讓小猴子們按照香蕉數(shù)量從大到小進(jìn)行排序，那么你可以用新學(xué)到的桶排序算法來(lái)幫助猴媽媽解決問(wèn)題嗎？

桶排序也稱為箱排序，它的原理是將數(shù)組分到有限數(shù)量的桶中，再對(duì)桶進(jìn)行排序。相關(guān)知識(shí)推薦您復(fù)習(xí)第44期的《趣味數(shù)學(xué)——鴿巢問(wèn)題》。在猴子與香蕉問(wèn)題中，最多的一只猴子摘了7串香蕉，我們便需要準(zhǔn)備八個(gè)桶，每個(gè)桶代表一種香蕉的數(shù)量（0串香蕉、1串香蕉、2串……7串香蕉一共8個(gè)桶）。然后把香蕉按數(shù)量放進(jìn)對(duì)應(yīng)的桶里，所有的香蕉放置完畢后，從最后一個(gè)桶里（7串香蕉）開(kāi)始查詢桶里面是否有香蕉存在。如果有，那么數(shù)量最多的就是7串香蕉。然后看6串的桶里是否有香蕉，這樣從7到0依次取出便完成了排序（如圖1）。

這時(shí)你應(yīng)該發(fā)現(xiàn)5串香蕉的桶里有兩只猴子摘的香蕉，當(dāng)兩個(gè)猴子數(shù)字相同該怎么處理呢？是疊加還是合并呢？接下來(lái)我們用Scratch代碼把桶排序的過(guò)程給大家演示一遍你就知道了。

首先我們新增加兩個(gè)列表“八個(gè)桶”和“香蕉數(shù)量”。桶的數(shù)量根據(jù)最多香蕉的數(shù)量加1就可以了。桶列表用來(lái)演示香蕉放入桶中的過(guò)程。首先我們將香蕉列表和桶列表全部都清空，然后隨機(jī)產(chǎn)生五個(gè)香蕉的數(shù)量，接下來(lái)就是用自定義積木“桶排序”對(duì)香蕉數(shù)量進(jìn)行排序（圖2）。

桶排序開(kāi)始時(shí)，我們新增一個(gè)變量“序號(hào)”用來(lái)進(jìn)行標(biāo)記，默認(rèn)初始值為1。重復(fù)執(zhí)行5次，每次執(zhí)行一次序號(hào)加1。依次將香蕉列表中每一項(xiàng)的值有序地添加到桶的列表中去，如果與列表中已有數(shù)值重復(fù)，桶列表中的數(shù)值不能覆蓋，而是用空格隔開(kāi)添加在后面（圖3）。運(yùn)行后桶列表中效果如圖4。

添加完成后，將序號(hào)設(shè)為8，代表從桶列表最后一項(xiàng)開(kāi)始提取，判斷每項(xiàng)值是否為空，如果存在數(shù)值便輸出結(jié)果，如果不存在數(shù)值跳過(guò)該項(xiàng)，每判斷一次將序號(hào)減1代表從數(shù)量最多的一個(gè)桶開(kāi)始統(tǒng)計(jì)，依次遞減直到數(shù)量最少的桶（圖5）。

循環(huán)結(jié)束后把排序后的結(jié)果說(shuō)出來(lái)（圖6）。

學(xué)會(huì)懂桶排序后你會(huì)發(fā)現(xiàn)桶排序是最簡(jiǎn)單最容易理解的排序算法了，但是這種容易理解的排序方法有個(gè)缺點(diǎn)，其復(fù)雜度與值域息息相關(guān)。當(dāng)值域很大而且分布不均勻時(shí)就需要增加太多無(wú)用的桶，排序的輪數(shù)增加太多，效率就隨之大大降低了。