桶排序

◎曹曉敏

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

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

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

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

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

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

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

曉敏老師：

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

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

圖1

圖2

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

圖3

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

圖4

圖5

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

圖6

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

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

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

掃描下方小程序碼，看看長沙市芙蓉區(qū)馬坡嶺小學學生的優(yōu)秀作品吧！

程序作品1：射擊游戲作者：王奕辰

程序作品2：愉悅水桶作者：王奕辰