桶排序

嶺童小子很能干，常常幫助老師們做一些力所能及的事情。例如，每周五他都幫班主任統計每個同學獲得的貼紙數量，并給大家排序。全班有45個同學，每個星期都要統計、排序，還不能出一丁點差錯，這項任務可不輕松。而且，手工統計不僅麻煩、費時，還容易出錯。有沒有更好的辦法呢？

嶺童小子思考了很久也沒想出來，他有點著急了。看著嶺童小子眉頭緊鎖的樣子，一旁的星空樂了。

我來幫幫你吧。每個同學最多能得到多少個貼紙，請告訴我。

一個星期內，每個同學最多能得到100個貼紙。

好。請依次告訴我每個同學的貼紙數量。

嶺童小子將每個同學的貼紙數量依次告訴星空……說完最后一個同學的貼紙數量，星空立馬把同學們的貼紙數量按照從少到多的順序排列了出來。

“怎么樣？”星空得意地看著嶺童小子。而此時的嶺童小子腦袋都是蒙的，他需要好好想一想……

曉敏老師：

哈哈，嶺童小子別著急。我們將問題簡化一下：假設每個同學最多能獲得10個貼紙，班上有5個同學，他們的貼紙數量分別為1、7、3、5、9，請找出貼紙數量最多的3個同學。對于這個問題，我們一眼就能看出答案，但是如何用編程的方法來解決呢？

第一步，準備10個空桶子，將它們按照1—10進行編號。將每個桶子標記為0，表示桶子是空的，如圖1。代碼見圖2，此時的循環控制變量既控制循環次數，又與桶子編號重疊。

第二步，輸入第1個同學的貼紙數量1。將1號桶標記為1，表示桶子不是空的。輸入第2個同學的貼紙數量7。將7號桶標記為1，表示桶子不是空的。如圖3。

第三步，依次輸入5個同學的貼紙數量，將相關的桶子標記為1，如圖4。代碼見圖5，此時的循環控制變量控制循環次數。因為有5個同學，所以循環5次，依次輸入每個同學的貼紙數量。

第四步，按照10—1倒序檢索桶子，檢索到的前三個標記為1的桶子，即9號桶、7號桶、5號桶，這三個桶子對應的同學就是貼紙數量最多的3個同學。代碼見圖6，此時的循環控制變量指桶子編號。

說明：計數器的初始值為1，我們需找到貼紙數量最多的三個同學，所以，重復執行直到計數器為4即可。

同學們，在對一組數據進行排序時，如果知道數據的上限，你就可以用這種方法來排序。將數據分別放入各個桶子，借助桶子的位置完成排序。這就是桶排序算法的基本思路。你看懂了嗎？

其實，這里我們忽略了一個問題 ：如果有兩個同學得到的貼紙數量相同，那該怎么辦呢？同學們可以進一步思考哦。

曹曉敏 ：湖南省特級教師，湖南省優秀科技輔導員，長沙市首批卓越教師，長沙市骨干教師，長沙市芙蓉區馬坡嶺小學信息技術教師。