桶排序（Bucket sort） 或所谓的 箱排序 ，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到O(n log n)下限的影响。

• 定义

假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。

• 算法原理

1. 设置一个定量的数组当作空桶子。

2. 寻访序列，并且把项目一个一个放到对应的桶子去。

3. 对每个不是空的桶子进行排序。可以继续使用桶排序或者其他排序算法，如插入排序

4. 从不是空的桶子里把项目再放回原来的序列中。

其 伪代码 为：

• Java实现源码解析

首先，创建方法用于排序指定序列，该方法中包含两个步骤

1. 获取到待排序的 数列 中最大值对应的待除的值-divisionValueOfSequence， 这个参数的作用是用来告诉我们，当前我们需要排序的是数列中的那一位数字(个/十/百/千位…)

2. 调用子方法用来排序，改排序是按照待排序数值中指定位数的数值排序

其中getDivisionValueOfSequence方法实现如下：

其次，按照指定的数位来排序，待排序的数位可以通过divisionValueOfSequence求得，改执行关键点为：

1. value/divisionValue%10公式biaoshi 获取到指定的位数上的值，值为0-9，然后将它作为桶的序号

2. 在放入到对应的桶中后，还需要对桶中的集合做排序(迭代调用)

3. 最后需要将桶中排序好的值放入到原始值中

可以看出，桶排序其实是参考一个规律来排序的： 一个数组的index其实也是排序好的 。按照这种逻辑，只要我们按照指定规则将数据放到对应的排序位置中，那么结果就排序好了

另外，这个实现中为了简单，创建的bucketArray比较多，而实际应用中，bucketarray还有优化空间。

• 限制与应用场景

桶排序的复杂度信息为：

桶排序复杂度

桶排序的限制：

1. 数据的长度通常要求一样，或者可以转换成同类型

2. 其是通过映射来做排序的，所以需要定义中间变量来保存中间值

其应用场景：

1. 待排序数据比较集中

2. 数据量很大，通过其他比较排序算法比较次数过多

完整代码请查看地址：

如果这对你有用，粉我吧，每天都有干货哦