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

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。

桶排序

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

算法步骤

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

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

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

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

算法演示

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

imageimage

排序动画过程解释

  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++代码实现

imageimage

Java代码实现

imageimage

JavaScript代码实现

imageimage

关键词:排序 数字 数据 代码 插入 算法 动画 一个 实现 使用

相关推荐:

十大经典排序算法动画与解析,看我就够了!(配代码完全版)

五分钟学会一个高难度算法:快速排序

动画+原理+代码,解读十大经典排序算法

算法初级02——荷兰国旗问题、随机快速排序、堆排序、桶排序、相邻两数的最大差值问题、工程中的综合排序算法

基础排序算法总结

JavaScript十大经典排序算法

十大经典排序算法(动图演示)(转载)