五分钟看懂一个有意思的排序：桶排序

[CoderOnePolo]

桶排序

桶排序(Bucket sort)是一种基于计数的排序算法（计数排序可参考上节的内容），工作的原理是将数据分到有限数量的桶子里，然后每个桶再分别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）

你可以关注公众号 五分钟学算法 获取更多排序内容。

算法步骤

1. 设置固定数量的空桶。

2. 把数据放到对应的桶中。

3. 对每个不为空的桶中数据进行排序。

4. 拼接不为空的桶中数据，得到结果。

算法演示

动画演示 GIF 加载有点慢，请稍等片刻^_^

排序动画过程解释

1. 首先，设置固定数量的空桶，在这里为了方便演示，设置桶的数量为 5 个空桶

2. 遍历整个数列，找到最大值为 56，最小值为 2，每个桶的范围为 （ 56 - 2 + 1 ）/ 5 = 11

3. 再次遍历整个数列，按照公式 floor((数字 – 最小值) / 11) 将数字放到对应的桶中

4. 比如，数字 7 代入公式 floor((7 – 2) / 11) = 0 放入 0 号桶

5. 数字 12 代入公式 floor((12 – 2) / 11) = 0 放入 0 号桶

6. 数字 56 代入公式 floor((56 – 2) / 11) = 4 放入 4 号桶

7. 当向同一个索引的桶，第二次插入数据时，判断桶中已存在的数字与新插入数字的大小，按照左到右，从小到大的顺序插入（可以使用前面讲解的插入排序）实现

8. 比如，插入数字 19 时，1 号桶中已经有数字 23，在这里使用插入排序，让 19 排在 23 前面

9. 遍历完整个数列后，合并非空的桶，按从左到右的顺序合并 0，1，2，3，4 桶。

10. 这样就完成了 桶排序

代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画，笔者将贴出多种编程语言的参考代码，代码全部来源于网上。

C++代码实现

Java 代码实现

JavaScript 代码实现

你可以关注公众号 五分钟学算法 获取更多排序内容。

[stevenbipt]

点个赞~

[wysnylc]

桶的数量可以随样本的大小增加或者减少

[chanchan]

不说说为什么这么排以及这么排的优点缺点吗

[Geraltt]

想知道时空复杂度的推导

[flowfire]

这个排序方法最坏情况下的复杂度不是跟插入排序一样么……

[CoderOnePolo]

@wysnylc 是的

[wysnylc]

@chanchan #3 可以分布式处理,避免在内存中一次加载超大量数据
@flowfire #5 实际应用不只是考虑复杂度,要考虑生产环境的限制比如内存硬盘 CPU

[stevenbipt]

@Geraltt #4 算法导论上有完整的推导

[stevenbipt]

@flowfire #5 使用插入排序没问题的，只要数据满足：所有桶的大小的平方和与总的元素数呈线性关系，桶排序的期望运行时间为 O(N)