趣味數學——桶排序

陳新龍

我們已經講過多種排序的算法，都是利用不同的數學方法對數組列表進行排序，比如冒泡排序、選擇排序……今天分享的排序算法名為桶排序，是數據結構算法中一種簡單高效并且容易理解的算法。

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

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

這時你應該發現5串香蕉的桶里有兩只猴子摘的香蕉，當兩個猴子數字相同該怎么處理呢？是疊加還是合并呢？接下來我們用Scratch代碼把桶排序的過程給大家演示一遍你就知道了。

首先我們新增加兩個列表“八個桶”和“香蕉數量”。桶的數量根據最多香蕉的數量加1就可以了。桶列表用來演示香蕉放入桶中的過程。首先我們將香蕉列表和桶列表全部都清空，然后隨機產生五個香蕉的數量，接下來就是用自定義積木“桶排序”對香蕉數量進行排序（圖2）。

桶排序開始時，我們新增一個變量“序號”用來進行標記，默認初始值為1。重復執行5次，每次執行一次序號加1。依次將香蕉列表中每一項的值有序地添加到桶的列表中去，如果與列表中已有數值重復，桶列表中的數值不能覆蓋，而是用空格隔開添加在后面（圖3）。運行后桶列表中效果如圖4。

添加完成后，將序號設為8，代表從桶列表最后一項開始提取，判斷每項值是否為空，如果存在數值便輸出結果，如果不存在數值跳過該項，每判斷一次將序號減1代表從數量最多的一個桶開始統計，依次遞減直到數量最少的桶（圖5）。

循環結束后把排序后的結果說出來（圖6）。

學會懂桶排序后你會發現桶排序是最簡單最容易理解的排序算法了，但是這種容易理解的排序方法有個缺點，其復雜度與值域息息相關。當值域很大而且分布不均勻時就需要增加太多無用的桶，排序的輪數增加太多，效率就隨之大大降低了。