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

桶排序

桶排序(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 代码实现

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