一组动画彻底理解桶排序

桶排序

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

算法步骤

设置固定数量的空桶。

把数据放到对应的桶中。

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

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

算法演示

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

排序动画过程解释

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

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

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

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

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

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

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

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

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

这样就完成了桶排序

代码实现

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

C++代码实现

Java代码实现

JavaScript代码实现

●编号800，输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

人工智能与大数据技术

更多推荐《25个技术类公众微信》

涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。