桶排序

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

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

我來(lái)幫幫你吧。每個(gè)同學(xué)最多能得到多少個(gè)貼紙，請(qǐng)告訴我。

一個(gè)星期內(nèi)，每個(gè)同學(xué)最多能得到100個(gè)貼紙。

好。請(qǐng)依次告訴我每個(gè)同學(xué)的貼紙數(shù)量。

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

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

曉敏老師：

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

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

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

第三步，依次輸入5個(gè)同學(xué)的貼紙數(shù)量，將相關(guān)的桶子標(biāo)記為1，如圖4。代碼見圖5，此時(shí)的循環(huán)控制變量控制循環(huán)次數(shù)。因?yàn)橛?個(gè)同學(xué)，所以循環(huán)5次，依次輸入每個(gè)同學(xué)的貼紙數(shù)量。

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

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

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

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

曹曉敏 ：湖南省特級(jí)教師，湖南省優(yōu)秀科技輔導(dǎo)員，長(zhǎng)沙市首批卓越教師，長(zhǎng)沙市骨干教師，長(zhǎng)沙市芙蓉區(qū)馬坡嶺小學(xué)信息技術(shù)教師。