x-note
Search…
Introduction
FE
正则表达式
Git
基础算法
冒泡排序
插入排序
选择排序
快速排序
归并排序
希尔排序
堆排序
桶排序
计数排序
基数排序
二叉树的遍历
HTTP
Protocol Buffers
gRPC
设计模式
Powered By GitBook
桶排序
桶排序（Bucket sort）又称之为箱排序，将数组中的元素分到有限数量的桶里，再对桶内的元素进行排序，最终将非空的桶内的已排序数组合并。
对桶内元素进行排序时，可以采取其它的排序算法。
  • 平均时间复杂度：
    O(n+k)\mathcal{O}(n + k)
    ​
  • 最好时间复杂度：
    O(n+k)\mathcal{O}(n + k)
    ​
  • 最坏时间复杂度：
    O(n2)\mathcal{O}(n^2)
    ​
  • 空间复杂度：
    O(n∗k)\mathcal{O}(n * k)
    ​
  • 稳定性：对桶内元素采取的排序算法导致稳定性无法确定
  • 排序方式：非原地（not-in-place）
Could not load image
Could not load image
步骤：
  1. 1.
    设置一个定量的数组当作空桶
  2. 2.
    遍历序列，将元素放入对应的桶里
  3. 3.
    对每个不是空的桶进行排序
  4. 4.
    从非空的桶里将元素放回原来的序列中。
JavaScript 实现：
function bucketSort(arr, step = 1) {
const minVal = Math.min(...arr);
const maxVal = Math.max(...arr);
​
// 查找元素所属的桶的下标
const findElementBucketIndex = item => Math.floor((item - minVal) / step);
​
const bucketNum = findElementBucketIndex(maxVal) + 1; // 桶的数量
const buckets = []; // 所有桶的集合
// const buckets = new Array(bucketNum);
​
// 初始化桶
for (let i = 0; i < bucketNum; ++i) {
buckets[i] = [];
}
​
// 将元素放入指定的桶中
arr.forEach((item) => {
const bucketIndex = findElementBucketIndex(item); // 元素所属的桶的下标
buckets[bucketIndex].push(item);
})
​
arr.splice(0); // 清空数组，也可以使用新的空间进行处理
​
buckets
.filter(item => item.length > 0) // 过滤空的桶
.forEach(item => {
// 对桶内元素排序
// 此处可采取任意排序算法，因此采用系统默认排序算法替代
item.sort();
arr.push(...item);
})
​
return arr;
}
Previous
堆排序
Next
计数排序
Last modified 3yr ago
Copy link