桶排序（又称箱排序）是一种基于分治思想、效率很高的排序算法，理想情况下对应的时间复杂度为 O(n)。
接下来，我们系统地学习一下桶排序算法。
桶排序算法的实现思路
假设一种场景，对 {5, 2, 1, 4, 3} 进行升序排序，桶排序算法的实现思路是：
- 准备 5 个桶，从 1~5 对它们进行编号；
- 将待排序序列的各个元素放置到相同编号的桶中；
- 从 1 号桶开始，依次获取桶中放置的元素，得到的就是一个升序序列。
整个实现思路如下图所示：
桶排序算法中，待排序的数据量和桶的数量并不一定是简单的“一对一”的关系，更多场景中是“多对一”的关系，例如，使用桶排序算法对 {11, 9, 21, 8, 17, 19, 13, 1, 24, 12} 进行升序排序，实现过程如下图所示：
待排序序列中有 10 个元素，但算法中只用了 5 个桶，因此有些桶需要存放多个元素。实际场景中，我们可以自定义各个桶存放元素的区间（范围），比如上图中第一个桶存放 [0,5) 区间内的元素，第二个桶存放 [6,10) 之间的元素。
当存在“一个桶中有多个元素”的情况时，要先使用合适的排序算法对各个痛内的元素进行排序，然后再根据桶的次序逐一取出所有元素，最终得到的才是一个有序序列。
总之，桶排序算法的实现思路是：将待排序序列中的元素根据规则分组，每一组采用快排、插入排序等算法进行排序，然后再按照次序将所有元素合并，就可以得到一个有序序列。
桶排序算法的具体实现
假设用桶排序算法对 {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51} 进行升序排序，采用的分组规则是：将所有元素分为 10 组，每组的标号分别为 0~9。对序列中的各个元素乘以 10 再取整，得到的值即为该元素所在组的组号。
