再谈桶排排序算法—从计数排序到桶排序
Author：zhoulujun Date：
桶排序（Bucket sort）或所谓的箱排序是利用编号分组存储数字，再利用编号合并分组的一种算法排序。其实现过程大致如下：
将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。
其实桶排序就是一种归纳排序，他将要进行排序的数组分到有限的桶里面，然后对桶进行归纳排序，可以理解成他是一个归纳结果。桶排序可以看做计数排序的升级版
回顾计数排序算法
上篇《再谈计数排序—看了多篇文件理解记忆总结—排序算法 》，计数排序是一种稳定的排序，是一种牺牲空间换取时间的做法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。
总结如下：
计数排序算法过程如下：
根据待排序集合中最大元素和最小元素的差值范围，申请额外空间
花 O(n)的时间扫描一下整个序列 A，获取最小值min和最大值max，开辟一块新的空间创建新的数组B，长度为 max - min + 1（因为申请的额外空间足以将 min 和 max 之间的所有元素记录，将待排序集合中每一个元素都记录到额外空间上）
遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内；
组 B 中 index 的元素记录的值是 A 中某元素出现的次数
对额外空间内数据进行计算，得出每一个元素的正确位置；
将待排序集合每一个元素移动到计算得出的正确位置上。
但是，计数排序不适用于跨度很大或者浮点数，那么有没有可以处理浮点类型的稳定排序呢？桶排序就是。
桶排序与计数排序对比
当然桶排序更是对计数排序的改进，计数排序申请的额外空间跨度从最小元素值到最大元素值，若待排序集合中元素不是依次递增的，则必然有空间浪费情况。桶排序则是弱化了这种浪费情况，将最小值到最大值之间的每一个位置申请空间，更新为最小值到最大值之间每一个固定区域申请空间，尽量减少了元素值大小不连续情况下的空间浪费情况。
桶排序与快速排序对比
快速排序是将集合拆分为两个值域，这里称为两个桶，再分别对两个桶进行排序，最终完成排序。桶排序则是将集合拆分为多个桶，对每个桶进行排序，则完成排序过程。两者不同之处在于，快排是在集合本身上进行排序，属于原地排序方式，且对每个桶的排序方式也是快排。桶排序则是提供了额外的操作空间，在额外空间上对桶进行排序，避免了构成桶过程的元素比较和交换操作，同时可以自主选择恰当的排序算法对桶进行排序。
桶排序的基本原理
首先说一下桶排序的桶是什么概念，这里的“桶”是一个区间范围，里面可以承载一个或多个元素。桶排序的第一步就是确定桶的个数和区间。具体的建立多少个桶、每个桶的区间范围是多少，有不同的方式，我们这里使用桶的数量等于原始数列的元素的数量（为什么等于数列的数量，后面会讲到）。除了最后的一个桶只包含最大值，其他的值分散在其他桶里。
适应范围：
适应外部排序，即数据量比较大，但是数据范围比较小的排序
基本思想
桶排序的思想近乎彻底的分治思想。
桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。
然后基于某种映射函数f ，将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素 (每个桶B[i]都是一组大小为N/M 的序列 )。
接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列。
补充： 映射函数一般是 f = array[i] / k; k^2 = n; n是所有元素个数
为了使桶排序更加高效，我们需要做到这两点：
在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
桶排序过程中存在两个关键环节：
元素值域的划分，也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择，若规则设计的过于模糊、宽泛，则可能导致待排序集合中所有元素全部映射到一个桶上，则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛，则可能导致待排序集合中每一个元素值映射到一个桶上，则桶排序向计数排序方式演化。
排序算法的选择，从待排序集合中元素映射到各个桶上的过程，并不存在元素的比较和交换操作，在对各个桶中元素进行排序时，可以自主选择合适的排序算法，桶排序算法的复杂度和稳定性，都根据选择的排序算法不同而不同。
桶排序逻辑实现-算法步骤
第一步，确定桶的个数和区间。直接指定，或者根据一定映射规则计算，比如：
桶个数=根据待排序集合中最大元素和最小元素的差值范围和映射规则，
区间跨度 = （最大值-最小值）/ （桶的数量 - 1）桶的各式各样
第二步，把原始数列的元素放入对应的桶中
第三步，对每个不为空的桶中数据进行排序。
第四步，拼接不为空的桶中数据，输出元素
桶排序的复杂度
假设原始数列的元素个数是N，桶的数量的M，平均每个桶内的元素数量的N/M求最值，计算量N
初始化桶，计算量M
数列的元素放入桶，计算量N
每个桶内元素排序，由于使用了O(n log n)算法，计算量是M(N/M * log N/M)=N(log N/M)
最后返回排好序的集合，计算量是N
综上所述，计算量是 3N+M+ N(log N - log M)，去掉系数O(N+M+N(log N - log M))
时间复杂度：O(n+k)，k为 n*logn-n*logm
平均时间复杂度：O(n + k)
最佳时间复杂度：O(n + k)
最差时间复杂度：O(n ^ 2)
空间复杂度：很明显是原始数组的空间N 加上 桶的空间M，是N+M
算法稳定性：桶排序是一种稳定排序算法。
是否是原地算法：非原地算法，不属于 In-place
桶排序的缺陷
假如元素分布极不均衡，比如全部在最后一个桶内，则此时的时间复杂度就退化到了O(n*log n)，并且空间复杂度浪费了很多，因为创建了很多无用的空桶。
桶排序案列
举个易于理解的例子：
一组数字，9,3,4,0,2,8,5,1,7,6,11,10,18,15,17,12,16,13,19,14
我们把这组数字分组编号成10个桶装起来，但怎么编号分组呢？
这里我们利用数字范围来对数字进行分桶。
首先，最大数减去最小数，获取这组数字的取值范围，然后，我们让这个取值范围除以桶数，获取一个桶的取值范围，既然知道一个桶的取值范围，那么，通过对比每个数字占用多少个桶，我们就可以获取这个数字所对应的桶的编号了。（换一句话说，就是每个数字占用多少个取值范围，这里的桶其实就是数字的取值范围的具体化东西）
利用上面的例子做解释：
上面的最大值是19，最小值是0，所以这组数的取值范围是：19-0=19。
我们要用10个桶来分装这组数字，则一个桶的取值范围是：19 / 10 = 1.9。
所以，一个桶的取值范围就是：1.9。
知道了这些之后，我们怎么知道每个数字所对应的桶的编号呢？
我们让每个数字减去最小值再除以一个桶的取值范围就可以获得这个数字所对应的桶编号了，为什么这么说呢？因为我们就是利用数值范围来分桶的，所以理所当然的也是获取每个数字的取值范围来分桶的编号，而最小值就是我们的取值标准，当然是要每个数字都减去它才能准确的获取每个数的取值范围了。
根据上面的解释，那么，第一个数字的桶编号就是：(9-0) / 1.9 = 4.7368·······
当然为了确保编号为整数，我们必须给编号取整，这里我们是向上取整，所以第一个数：9的桶编号就是5啦。
其他的数字获取桶编号都是同样的原理，这里就不再重复叙述了。
桶排序JS实现
桶排序按照上面思路，JavaScript代码实现
function bucketSort (arr, splitCount) {
// 不是数组，直接返回
if (!Array.isArray(arr)) {
return arr
}
let length = arr.length
// 获取数组的长度，长度少于1，直接返回
if (length < 2) {
return arr
}
// 确定桶的个数和区间。区间跨度 = （最大值-最小值）/ （桶的数量 - 1）
let min = arr[0]
let max = arr[0]
// 默认桶的个数为3
splitCount = splitCount || 3
for (let i = 0; i < length; i++) {
if (i === 0) {
continue
}
if (arr[i] < min) {
min = arr[i]
}
if (arr[i] > max) {
max = arr[i]
}
}
//分成splitCount个桶，桶所占用的范围
let space = max - min
if (space === 0) {
return arr
}
let step = (space-1) / splitCount
const buckets = Array.from({length: splitCount}, () => [])
// 把原始数列的元素放入对应的桶中
for (let i = 0; i < length; i++) {
// 桶的数值减去最小数 min 获取的是桶占用的范围，再除以一个桶的范围，就是获取对应的桶编号
let index = Math.floor((arr[i] - min) / step)
buckets[index].push(arr[i])
// 空桶插入，直接返回
if (buckets.length === 1) {
continue
}
// 对数组进行插入排序
let arrTemp = buckets[index]
for (let j = arrTemp.length - 1; j > 0; j--) {
if (arrTemp[j] < arrTemp[j - 1]) {
let swap = arrTemp[j - 1]
arrTemp[j - 1] = arrTemp[j]
arrTemp[j] = swap
}
}
}
// 合并不为空的桶
return [].concat(...buckets)
}
let testArr = [9, 3, 4, 0, 2, 8, 5, 1, 7, 6, 11, 10, 18, 15, 17, 12, 16, 13, 19, 14, -5]
console.log(bucketSort(testArr, 3))参考文章：
JS桶排序的简单理解与实现方法示例 https://www.jb51.net/article/175002.htm
排序算法（九）：桶排序 https://www.jianshu.com/p/204ed43aec0c
算法：排序算法之桶排序 https://blog.csdn.net/developer1024/article/details/79770240
排序算法之桶排序的深入理解以及性能分析 https://www.cnblogs.com/dailc/archive/2016/12/03/6128823.html
JavaScript算法-桶排序 https://blog.csdn.net/an2766160/article/details/88532740
转载本站文章《再谈桶排排序算法—从计数排序到桶排序》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/8277.html