动画 | 什么是桶排序？

学过上一篇文章的计数排序之后，特别是归约化分治处理的计数排序（适用于较离散的非负整数序列）。计数排序的局限比较多，在排序之前需要解决负数和小数的问题，而桶排序不需要考虑这些。

桶排序和计数排序一样，不受O(nlogn)时间复杂度下限的影响，它将待排序序列通过遍历方式分到有限数量的桶中，然后每个桶被单独地排序，不管是使用同一个比较类排序算法或者使用不同的排序算法，或者还是递归地使用桶排序。桶排序可以通过比较方式实现，也可以通过非比较方式实现。

通过比较方式的桶排序分为4步工作步骤：

1.设定合适数量的分桶；

2.遍历待排序序列，将每个元素放入到对应的桶中；

3.对每个非空桶进行合适的排序算法；

4.按顺序访问桶，将桶中的元素依次放回到原序列中对应的位置。

关于如何设置合适数量的分桶，我们这里分为两种：设定简单的分桶和归约化的分桶。

设定简单的分桶

假设我们输入数组[13, 9, 15, 1, 7, 11, 25, 21, 29, 17, 5]，求数组中的最大值和最小值，max = 29，min = 1，设定分桶的情况为max / 10 – min / 10 + 1 = 3。所以我们设定合适的数量为3桶，从0开始。数组中第一个元素是13，进行(13 - min) / 10的运算，得2，放入到第3 个桶；数组中第2个元素是9，(9 - min) / 10 = 0，放入到第1个桶；依此类推。

分布完之后按顺序访问桶，将桶中的元素依次放回到原序列中对应的位置。