桶排序

2023-09-21 05:03曹晓敏
发明与创新 2023年27期
关键词:桶子小子星空

◎曹晓敏

岭童小子很能干,常常帮助老师们做一些力所能及的事情。例如,每周五他都帮班主任统计每个同学获得的贴纸数量,并给大家排序。全班有45 个同学,每个星期都要统计、排序,还不能出一丁点差错,这项任务可不轻松。而且,手工统计不仅麻烦、费时,还容易出错。有没有更好的办法呢?

岭童小子思考了很久也没想出来,他有点着急了。看着岭童小子眉头紧锁的样子,一旁的星空乐了。

我来帮帮你吧。每个同学最多能得到多少个贴纸,请告诉我。

一个星期内,每个同学最多能得到100 个贴纸。

好。请依次告诉我每个同学的贴纸数量。

岭童小子将每个同学的贴纸数量依次告诉星空……说完最后一个同学的贴纸数量,星空立马把同学们的贴纸数量按照从少到多的顺序排列了出来。

“怎么样?”星空得意地看着岭童小子。而此时的岭童小子脑袋都是蒙的,他需要好好想一想……

晓敏老师:

哈哈,岭童小子别着急。我们将问题简化一下:假设每个同学最多能获得10 个贴纸,班上有5 个同学,他们的贴纸数量分别为1、7、3、5、9,请找出贴纸数量最多的3 个同学。对于这个问题,我们一眼就能看出答案,但是如何用编程的方法来解决呢?

第一步,准备10 个空桶子,将它们按照1—10 进行编号。将每个桶子标记为0,表示桶子是空的,如图1。代码见图2,此时的循环控制变量既控制循环次数,又与桶子编号重叠。

图1

图2

第二步,输入第1 个同学的贴纸数量1。将1 号桶标记为1,表示桶子不是空的。输入第2 个同学的贴纸数量7。将7 号桶标记为1,表示桶子不是空的。如图3。

图3

第三步,依次输入5 个同学的贴纸数量,将相关的桶子标记为1,如图4。代码见图5,此时的循环控制变量控制循环次数。因为有5 个同学,所以循环5 次,依次输入每个同学的贴纸数量。

图4

图5

第四步,按照10—1 倒序检索桶子,检索到的前三个标记为1 的桶子,即9 号桶、7 号桶、5 号桶,这三个桶子对应的同学就是贴纸数量最多的3 个同学。代码见图6,此时的循环控制变量指桶子编号。

图6

说明:计数器的初始值为1,我们需找到贴纸数量最多的三个同学,所以,重复执行直到计数器为4 即可。

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

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

扫描下方小程序码,看看长沙市芙蓉区马坡岭小学学生的优秀作品吧!

程序作品1:射击游戏作者:王奕辰

程序作品2:愉悦水桶作者:王奕辰

猜你喜欢
桶子小子星空
炫酷小子
好动小子王妥妥
别人家的虎小子(下)
星空
机智题
你也爱吃仰望星空派吗?
星空
超级小子
破裂的水桶