编程中梳理桶排序的逻辑

1. 什么是桶排序，它和希尔排序的区别是什么

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

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

区别就是桶排序要求数据的长度必须完全一样，而希尔排序是非稳定排序算法。

2. 桶式排序

桶式排序不再是一种基于比较的排序方法，它是一种非常巧妙的排序方式，但这种排序方式需要待排序列满足如下两个特征：

下面介绍桶式的详细过程，以如下待排序列为例。
5、4、2、4、1
这个待排序列处于0、1、2、3、4、5这个可枚举范围内，而且这个范围也很小，正是桶式排序待派用场之时。
具体步骤如下。
(1)对这个可枚举范围构建一个buckets数组，用于记录“落入”每个桶中的元素的个数，于是可以得到下图所示的buckets数组。

(2)对图中所示的buckets数组的元素进行重新困备计算，按如下公式进行重新计算。
buckets[i]=buckets[i]+buckets[i-1] ；（其中1<= i < buckets.length）
即得到下图所示的buckets数组。

上面理论还有点抽象。以待排序列中最后一个元素1为例，找到新buckets数组中元素1对应桶的值，该值为1，这表明元素1就应该排在第1位；再以待排码返序列中倒数第2个元素4为例，找到新buckets数组中元素4对应桶的值，该值为4，这表明元素4就应该排在第4位……依此类推。

桶式排序是一种非常优秀的排序算法，时间效率极高，
它只要经过2轮遍历：
第1轮遍历待排数据，统计每个待排数据“落入”各桶中的个数；
第2轮遍历用于重新计算每个buckets数组元素的值。
2 轮遍历后就可得到每个待排数据在有序序列中的位置，然后将各个数据项一次放入指定位置即可。
桶式排序的空间开销较大，它需要两个数组：第1个buckets数组用于记录“落入”各桶中元素的个数，进而保存各元素在有序序列中的位置；第2个数组用于缓存待迟尺饥排数据。

桶式排序是稳定的。

3. 桶排序与哈希桶排序

桶排序 (箱排序)的原理是将待排序序列分到有限数量的桶里面，然后对每个桶再分别排序（帆禅咐可以使用其它的排序算法或者是递归使用桶排序算法），最后将各个桶中的数据有序的合并起来成为一个整体有序的序列。
排序过程：
1.假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
2.将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
3.将各个桶中的数据有序的合并起来

设有数组 array = [29, 25, 3, 49, 9, 37, 21, 43]，那么数组中最大数为 49，先设置 5 个桶，那么每个桶可存放数的范围为：09、1019、2029、3039、40~49，然后分别将这些数放人自己所属的桶，如下图：

1.时间复杂度：O(m+n)
2.空间复杂度：O(m+n)

适用于序列比较均匀的情况，否则会很耗空间。
或者特殊的场景，例如需要对一个公司的员工的年龄进行排序，年龄的范围为1-120，此时就可以开辟120个桶进行统计排序。
另，桶排序的瓶颈主要是桶数量的选择。
另此算法为稳定的排序算法。

排序算法主要是用分治法，用哈希函数对序列进行划分，最后使用其它的排序算法或者递归使用哈希排序进行排序从而得到一个整体有序的序列。下面先介绍几个自定义的概念：
1.哈希桶排序：因为本算法是使用了哈希函数把序列划分到对应的桶里面，所以本排序算法取名为哈希桶排序。
2.哈希桶因子（hashFactor）：hashFactor = （max - min） / length
计算公式如上式，当结果小于等于0的时候再做特殊处理，据此因子进行桶的划分。

设有数组 array = [10011, 10001, 16, 14, 12, 10000, 10, 10002, 10003, 1]，那么数组中最大值max = 10011，最小值min = 1，哈希桶因子hashFactor = （10011 - 1） / 10 = 1001。对数组进行划分，10011 / 1001 = 10，所以10011放在keywei10的桶里面；10001 / 1001 = 9， 所以10001放在key为9的桶里面，以此类推，最后得到的桶态纯的情况为：{0=[1, 10, 12, 14, 16], 9=[10000, 10001, 10002, 10003], 10=[10011]}。再分别对每个桶进行排序即可。

1.时间复杂度：O(m+n)
2.空间复杂度：O(m+n)

此算法与桶排序对比，主要是通过哈希建桶的方式减少了空间的消耗，对序列进行了一个归约袭伍，时间上跟桶排序相当。
使用与序列的最小最大值相差比较大同时又出现在某一个取值区间的集聚的情况。
另此算法为稳定的排序算法。

4. 桶排序怎么实现

桶排序的实验如下：

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别皮明的排序算法或是以递归方式继续使用桶排序进行排序）。

桶排序是鸽巢运拿排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到O(nlogn) 下限的影响。

处理大量重复元素的情况：对于存在大量重复元素的情况，桶排序的效率也会比其他排序算法高。因为桶排序在统计每个元素出现次数的过程中，相同元素只需计数一次，并存放在同一个桶里，不需要进行额外的比较和交换操作。

作为其他排序算法的优化：桶排序还可以作为其他排序算法的优化，提高其排序效率。比如，在快速排序中，每次选取的枢轴元素可能会导致某些分区的长度远大于另一些分区，这就会影响快排的效率。此时可以使用桶排序对枢轴元素进行预处理，将数据分成若干个区域，再对燃悄告每个区域内的元素进行快排。