js实现基数算法
基数排序（Radix Sort）实现
基数排序是一种非比较型整数排序算法，通过逐位分配和收集实现排序。以下是JavaScript的实现方法及说明：
算法原理
基数排序基于键值的每位数字进行排序，从最低位（LSD）或最高位（MSD）开始。通常使用桶分配和收集的步骤重复进行，直到所有位数处理完毕。
JavaScript实现代码
function radixSort(arr) {
const maxNum = Math.max(...arr) * 10;
let divisor = 10;
while (divisor < maxNum) {
let buckets = Array.from({ length: 10 }, () => []);
for (let num of arr) {
buckets[Math.floor((num % divisor) / (divisor / 10))].push(num);
}
arr = [].concat(...buckets);
divisor *= 10;
}
return arr;
}代码解析
-
初始化参数
maxNum确定循环次数，为数组中最大数的10倍（避免遗漏位数）。divisor初始为10，用于提取当前位的数字。
-
分配桶
- 创建10个空桶（对应数字0-9）。
- 计算当前位的值：
(num % divisor) / (divisor / 10)，将数字放入对应桶。
-
收集桶
- 按桶顺序合并所有数字，形成新的数组。
divisor乘以10，处理下一位。
示例调用
const array = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(array)); // 输出 [2, 24, 45, 66, 75, 90, 170, 802]时间复杂度
- 最佳/平均/最差：O(nk)，其中n是元素数量，k是最大数字的位数。
- 空间复杂度为O(n + k)，需要额外的桶空间。
注意事项
- 仅适用于整数排序，负数需特殊处理（如偏移量转换）。
- 对于位数差异大的数组，可能需补零或调整逻辑。
