趣味数学——桶排序

陈新龙

我们已经讲过多种排序的算法，都是利用不同的数学方法对数组列表进行排序，比如冒泡排序、选择排序……今天分享的排序算法名为桶排序，是数据结构算法中一种简单高效并且容易理解的算法。

猴妈妈带着5只小猴子去森林里摘香蕉，5只小猴子分别摘了5、2、5、3、7串香蕉。猴妈妈想看看自己孩子们摘香蕉的成果，让小猴子们按照香蕉数量从大到小进行排序，那么你可以用新学到的桶排序算法来帮助猴妈妈解决问题吗？

桶排序也称为箱排序，它的原理是将数组分到有限数量的桶中，再对桶进行排序。相关知识推荐您复习第44期的《趣味数学——鸽巢问题》。在猴子与香蕉问题中，最多的一只猴子摘了7串香蕉，我们便需要准备八个桶，每个桶代表一种香蕉的数量（0串香蕉、1串香蕉、2串……7串香蕉一共8个桶）。然后把香蕉按数量放进对应的桶里，所有的香蕉放置完毕后，从最后一个桶里（7串香蕉）开始查询桶里面是否有香蕉存在。如果有，那么数量最多的就是7串香蕉。然后看6串的桶里是否有香蕉，这样从7到0依次取出便完成了排序（如图1）。

這时你应该发现5串香蕉的桶里有两只猴子摘的香蕉，当两个猴子数字相同该怎么处理呢？是叠加还是合并呢？接下来我们用Scratch代码把桶排序的过程给大家演示一遍你就知道了。

首先我们新增加两个列表“八个桶”和“香蕉数量”。桶的数量根据最多香蕉的数量加1就可以了。桶列表用来演示香蕉放入桶中的过程。首先我们将香蕉列表和桶列表全部都清空，然后随机产生五个香蕉的数量，接下来就是用自定义积木“桶排序”对香蕉数量进行排序（图2）。

桶排序开始时，我们新增一个变量“序号”用来进行标记，默认初始值为1。重复执行5次，每次执行一次序号加1。依次将香蕉列表中每一项的值有序地添加到桶的列表中去，如果与列表中已有数值重复，桶列表中的数值不能覆盖，而是用空格隔开添加在后面（图3）。运行后桶列表中效果如图4。

添加完成后，将序号设为8，代表从桶列表最后一项开始提取，判断每项值是否为空，如果存在数值便输出结果，如果不存在数值跳过该项，每判断一次将序号减1代表从数量最多的一个桶开始统计，依次递减直到数量最少的桶（图5）。

循环结束后把排序后的结果说出来（图6）。

学会懂桶排序后你会发现桶排序是最简单最容易理解的排序算法了，但是这种容易理解的排序方法有个缺点，其复杂度与值域息息相关。当值域很大而且分布不均匀时就需要增加太多无用的桶，排序的轮数增加太多，效率就随之大大降低了。