基本思想
- 桶排序使用「分而治之」的思想，将待排序数组分配到若干个桶内，然后再对每个桶各自执行一次排序任务；
- 桶内的排序可以使用不同的排序方法，每个桶内排序完成以后，依次将每个桶内的元素取出来，最终得到一个有序数组；
图解
将要排序的数分到几个大小相同的子区间里，这些子区间称为「桶」；
分别对每个桶里的数据进行排序（这里使用插入排序）；
按照顺序把各个桶中的元素依次取出；
适用范围
-
数据均匀分布，不会出现很多数落在同一个桶中的情况；
-
如果步长、桶数设置合理，每个桶使用插入排序，即能加快排序，又能保证数据的稳定性；
复杂度
-
时间复杂度：
- 平均时间复杂度
O(N) - 最差时间复杂度是：
O(N^2)，即：全部数据落在一个桶的时候；
- 平均时间复杂度
-
空间复杂度：
O(M)，这里 M 是一个相对笼统的概念，M 需要根据具体实现的细节来定，如果能够预知每个桶最多能装多少元素，可能这个 M 会很大，如果每个桶设置成为链式结构，M 的值会相对较小一些；
实现代码
function bucketSort(nums) {
// 第 1 步：找到数组中的最大值，以确定计数数组的长度
let max = Math.max(...nums);
let min = Math.min(...nums);
if (min < 0) {
throw new Error("该数组不适合使用桶排序");
}
// 第 2 步：计算出最大的数字有几位，这个数值决定了桶的个数
let maxLen = getMaxLen(max);
let step = 1000; // 默认步长
// 决定设置几个桶
if (maxLen < 5) {
// 如果最大数小于 10000
// 3 位数就设置 100 个桶
// 2 位数就设置 10 个桶
step = 10 ** (maxLen - 1);
}
// 桶的个数
let bucketLen = ((max / step) >> 0) + 1;
// 第 3 步：分桶
let temp = new Array(bucketLen).fill(0).map(it => []);
nums.forEach(num => {
// 找到所在的桶的索引
let bucketIndex = (num / step) >> 0;
// 在该桶中放入元素
temp[bucketIndex].push(num);
});
// 第 4 步：对于每个桶执行插入排序
temp.forEach(arr => insertionSort(arr));
// 第 5 步：从桶里依次取出来
nums.splice(0, nums.length, ...temp.flat());
}
// 插入排序
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let temp = arr[i];
let j = i;
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
// 获取一个整数的最大位数
function getMaxLen(num) {
let maxLoop = 0;
while (num > 0) {
num /= 10;
num >>= 0; // 向下取整
maxLoop++;
}
return maxLoop;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
非比较排序🔮 基数排序
上一篇
评论
