我想知道这是为什么 –费曼
桶排序：
先分类，把数据放进相应的桶里，然后对每个桶进行局部排序，最后再把桶排序一下
有四步:
1.创建桶
2.归类（把元素放到对应的桶里）
3.排序
4.合并
创建桶
1
2
3
4
5
6
7
8
9
10
|
let array = [3, 8, 6, 1, 5, 7, 9, 2, 4]
let min = Math.min(...array)
let max = Math.max(...array)
let size = 3
let count = Math.floor((max - min) / size) + 1 // count从1开始计算需要加1
let buckets = []
for (let i = 0; i < count; i++) {
buckets.push([])
}
console.log(buckets) // [ [], [], []]
|
归类
1
2
3
4
5
6
|
for (let value of array) {
let bucketIndex = Math.floor((vlaue - min) / size) // bucketIndex从0开始计算不需要加1
buckets[bucketIndex].push(value)
}
console.log(buckets) // [ [ 3, 1, 2 ], [ 6, 5, 4 ], [ 8, 7, 9 ] ]
|
排序 && 合并
排序用其他任一排序算法都可以，比如数据量不太大的时候，插入排序就比较适合
因为区间本来就是有序的，合并的时候直接链接这些数组就可以了
1
2
3
4
5
6
|
let result = []
for (let bucket of buckets) {
result.push(...insertionSort(bucket))
}
console.log(result) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
|
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
// 桶排序
function bucketSort(array, size = 10) {
let max = Math.max(...array)
let min = Math.min(...array)
let count = Math.floor((max - min) / size) + 1
let buckets = []
for (let i = 0; i < count; i++) {
buckets.push([])
}
for (let value of array) {
let bucketIndex = Math.floor((value - min) / size)
buckets[bucketIndex].push(value)
}
let result = []
for (let bucket of buckets) {
result.push(...insertionSort(bucket))
}
return result
}
// 插入排序
function insertionSort(array) {
for (let i = 1; i < length; i++) {
let j = i
let target = array[j]
while (j > 0 && array[j - 1] > target) {
array[j] = array[j - 1]
j--
}
array[j] = target
}
return array
}
|
复杂度 && 总结
桶排序是分布式排序，适合处理大批量数据。需要额外空间，是外部排序。
桶排序是否稳定，取决于第二步排序算法的选择。
时间复杂度是线性级 O(n)，可以简单理解：桶的范围大小是人为指定的，它不随数据规模变化，如果数据相对均匀分布，那么桶的个数就是核心影响因子了。
我创建了一个集合 jest 可以测试算法的靶场项目：
https://github.com/Llane00/algorithm-range-tests
将同步文章中的代码到这个项目下
使用 vscode 的读者可以安装拓展插件 jest，这个插件可以自动检测 test 文件自动运行，非常方便。
