x-note
Search…
桶排序
桶排序(Bucket sort)又称之为箱排序,将数组中的元素分到有限数量的桶里,再对桶内的元素进行排序,最终将非空的桶内的已排序数组合并。
对桶内元素进行排序时,可以采取其它的排序算法。
  • 平均时间复杂度:
    O(n+k)\mathcal{O}(n + k)
  • 最好时间复杂度:
    O(n+k)\mathcal{O}(n + k)
  • 最坏时间复杂度:
    O(n2)\mathcal{O}(n^2)
  • 空间复杂度:
    O(nk)\mathcal{O}(n * k)
  • 稳定性:对桶内元素采取的排序算法导致稳定性无法确定
  • 排序方式:非原地(not-in-place)
步骤:
  1. 1.
    设置一个定量的数组当作空桶
  2. 2.
    遍历序列,将元素放入对应的桶里
  3. 3.
    对每个不是空的桶进行排序
  4. 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!
Copy link