基本思想
- 是一种非比较的整数排序算法；
- 其原理是将整数按位数切割成不同的数字，然后对每个位数上的数字进行分别比较（低位优先）；
- 第一轮：先按个位数大小排序；
- 第二轮：再按十位数大小排序；
- 第 N 轮：再按 N 位数大小排序；
- 实际上也是一种桶排序，从 0 到 9 一共 10 个桶；
图解
复杂度
-
时间复杂度：
O(KN)，这里 N 为输入数组的长度，K 为一个数的位数； -
空间复杂度：
O(N+K)，这里 K（一个数的位数）通常比 N（输入数组的长度）小很多；
实现代码
function radixSort(nums) {
// 第 1 步：找出最大的数字
let max = Math.max(...nums);
let min = Math.min(...nums);
if (min < 0) {
throw new Error("该数组不适合使用基数排序");
}
// 第 2 步：计算出最大的数字有几位，就要做几次桶排序
let maxLoop = getMaxLen(max);
// 第 3 步：每一趟都使用计数排序
let countAry = new Array(10).fill(0); // 桶
let tempAry = new Array(nums.length); // 临时存储每一次桶排序的结果
for (let i = 0; i < maxLoop; i++) {
// 每一步都使用计数排序，保证排序结果是稳定的，这一步需要额外空间保存结果集，因此把结果保存在 tempAry 中
countingSort(nums, tempAry, 10 ** i, countAry);
nums.splice(0, nums.length, ...tempAry);
}
}
/**
* 计数排序
* @param nums 原始数组
* @param tempAry 存储每一次桶排序的结果
* @param divisors 用于取数的某一位
* @param countAry 计数数组
*/
function countingSort(nums, tempAry, divisor, countAry) {
// 内层循环得把数组从头到尾看一遍
nums.forEach(it => {
let remainder = ((it / divisor) >> 0) % 10; // 取数的某一位，先取个位，再十位、百位、...
countAry[remainder]++;
});
// 计数和，用于推断排序后的数组
for (let j = 1; j < 10; j++) {
countAry[j] += countAry[j - 1];
}
// 从后向前扫描，依次把看到的数写回 tempAry 数组，从后向前是为了保证稳定性
for (let j = nums.length - 1; j >= 0; j--) {
let remainder = ((nums[j] / divisor) >> 0) % 10;
let index = countAry[remainder] - 1; // 排序后的位置 = 计数和 - 1
tempAry[index] = nums[j]; // 把看到的数覆盖回去
countAry[remainder]--; // 前缀和减一，作为下一个看到的相同数存放位置的依据
}
// 重置数组 count，以便下次使用
countAry.fill(0);
}
// 获取一个整数的最大位数
function getMaxLen(num) {
let maxLoop = 0;
while (num > 0) {
num /= 10;
num >>= 0; // 向下取整
maxLoop++;
}
return maxLoop;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
非比较排序🔮 计数排序
上一篇
评论
