x-note
Search…
桶排序
桶排序（Bucket sort）又称之为箱排序，将数组中的元素分到有限数量的桶里，再对桶内的元素进行排序，最终将非空的桶内的已排序数组合并。
对桶内元素进行排序时，可以采取其它的排序算法。
- 平均时间复杂度：
- 最好时间复杂度：
- 最坏时间复杂度：
- 空间复杂度：
- 稳定性：对桶内元素采取的排序算法导致稳定性无法确定
- 排序方式：非原地（not-in-place）
步骤：
- 1.设置一个定量的数组当作空桶
- 2.遍历序列，将元素放入对应的桶里
- 3.对每个不是空的桶进行排序
- 4.从非空的桶里将元素放回原来的序列中。
JavaScript 实现：
1
function bucketSort(arr, step = 1) {
2
const minVal = Math.min(...arr);
3
const maxVal = Math.max(...arr);
4
5
// 查找元素所属的桶的下标
6
const findElementBucketIndex = item => Math.floor((item - minVal) / step);
7
8
const bucketNum = findElementBucketIndex(maxVal) + 1; // 桶的数量
9
const buckets = []; // 所有桶的集合
10
// const buckets = new Array(bucketNum);
11
12
// 初始化桶
13
for (let i = 0; i < bucketNum; ++i) {
14
buckets[i] = [];
15
}
16
17
// 将元素放入指定的桶中
18
arr.forEach((item) => {
19
const bucketIndex = findElementBucketIndex(item); // 元素所属的桶的下标
20
buckets[bucketIndex].push(item);
21
})
22
23
arr.splice(0); // 清空数组，也可以使用新的空间进行处理
24
25
buckets
26
.filter(item => item.length > 0) // 过滤空的桶
27
.forEach(item => {
28
// 对桶内元素排序
29
// 此处可采取任意排序算法，因此采用系统默认排序算法替代
30
item.sort();
31
arr.push(...item);
32
})
33
34
return arr;
35
}
Copied!
Last modified 3yr ago
Copy link