桶排序

岭童小子很能干，常常帮助老师们做一些力所能及的事情。例如，每周五他都帮班主任统计每个同学获得的贴纸数量，并给大家排序。全班有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即可。

同学们，在对一组数据进行排序时，如果知道数据的上限，你就可以用这种方法来排序。将数据分别放入各个桶子，借助桶子的位置完成排序。这就是桶排序算法的基本思路。你看懂了吗？

其实，这里我们忽略了一个问题 ：如果有两个同学得到的贴纸数量相同，那该怎么办呢？同学们可以进一步思考哦。

曹晓敏 ：湖南省特级教师，湖南省优秀科技辅导员，长沙市首批卓越教师，长沙市骨干教师，长沙市芙蓉区马坡岭小学信息技术教师。