看图轻松理解桶排序

推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种 排序 等等几十篇的样子。

桶排序

桶排序即Bucket Sort，也称箱排序。其基本思想是将待排序数组分配到若干个桶内，然后每个桶内再各自进行排序，桶内的排序可以使用不同的算法，比如插入排序或快速排序，属于分治法。每个桶执行完排序后，最后依次将每个桶内的有序序列拿出来，即得到完整的排序结果。

时间复杂度

设有n个元素，进行桶排序的时间复杂度分为两个部分：

1. 计算每个元素分配到哪个桶，时间复杂度是O(N)。
2. 假如在桶内使用快速排序，则时间复杂度为 ，其中 为第i个桶的数据量。

所以桶排序总的时间复杂度为两者之和。

排序要点

简单来看，桶排序的分治涉及到三部分：分、治、合。分，即将序列分成m个小序列；治，即对每个桶内的元素进行排序；合，即将每个桶合并到一起。

设待排序数组为a[0],a[1],...a[n-1]，并且假设数据符合均匀分布，桶排序步骤为：

1. 根据序列大小范围划分m个大小相同的区间，每个区间即是一个桶。
2. 将待排序的n个元素分发到对应区间的桶中，即是分操作。
3. 对每个桶包含的元素进行排序，可以使用快速排序或其他排序，即是治操作。
4. 每个桶都是有序序列，按桶顺序依次取出每个桶的元素，得到最终完整的有序数组，即是合操作。

桶的区间

既然是分开治理，那当然是每个桶都平均才更高效，所以最理想的状态是每个桶都分配到相同或很接近的数据量。可以设想在分配不均的情况下，桶中元素少的早已处理完而元素多的还得处理很长一段时间，导致效率低下。

但待排序数据并非总是均匀分布的，可能是正态分布或逻辑斯蒂分布之类的，此时为了能使每个桶的数据量均匀，桶的区间可以根据概率密度函数来确定。

排序过程

假设我们有如下10个元素，分别为 4, 7, 9, 13, 18, 1, 19, 11, 6, 15 。另外，假设我们的桶使用有序链表结构，现在进行桶排序。

首先先定义桶的数量及区间，因为待排序数组的最大元素与最小元素分别为19和1，那么总的范围区间可定义为[0,19]，假设用4个桶，则桶的区间分别为 [0,4][5,9][10,14][15,19] 。

开始将数组元素逐一分配到对应的桶中，第一个元素是4，分配到0号桶内。

第二个元素是7，分配到1号桶。

第三个元素是9，分配到1号桶，为了保证桶的有序链表，将9与7进行比较，

由于9大于7，于是9作为7的后继节点。

第四个元素是13，分配到2号桶。

第五个元素是18，分配到3号桶。

第六个元素是1，为保证桶的有序链表，1作为4的前驱结点。

第七个元素是19，为保证桶的有序链表，19作为18的后继结点。

类似的，将剩下的三个元素分配到对应的桶内，同时保证桶内为有序链表，最终结果如下。

现在每个桶都是一个有序序列，最后要执行合并操作，即按桶顺序依次取出每个桶的元素，最终完成整个序列的排序。

先取出0号桶的所有元素，分别为1、4。

接着取出1号桶的所有元素，分别为6、7、9。

继续取出2号桶的所有元素，分别为11、13。

最后取出3号桶的所有元素，分别为15、18、19。

至此完成整个排序工作。

-------------推荐阅读------------

我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、 mysql 协议、chatbot)

为什么写《Tomcat内核设计剖析》

我的2017文章汇总——机器学习篇

我的2017文章汇总——Java及中间件

我的2017文章汇总——深度学习篇

我的2017文章汇总——JDK源码篇

我的2017文章汇总——自然语言处理篇

我的2017文章汇总——Java并发篇

跟我交流，向我提问：

欢迎关注：