js实现基数算法
基数排序（Radix Sort）简介
基数排序是一种非比较型整数排序算法，通过逐位分配和收集实现排序。适用于整数或固定格式字符串，时间复杂度为O(nk)，其中n是元素数量，k是数字位数。
基数排序实现步骤
定义辅助函数 获取数字的指定位数，例如个位、十位等：
function getDigit(num, place) {
return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}计算数字的位数：
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}确定最大位数：
function mostDigits(nums) {
let maxDigits = 0;
for (let num of nums) {
maxDigits = Math.max(maxDigits, digitCount(num));
}
return maxDigits;
}主排序逻辑
function radixSort(nums) {
const maxDigits = mostDigits(nums);
for (let k = 0; k < maxDigits; k++) {
const buckets = Array.from({ length: 10 }, () => []);
for (let num of nums) {
const digit = getDigit(num, k);
buckets[digit].push(num);
}
nums = [].concat(...buckets);
}
return nums;
}使用示例
console.log(radixSort([23, 345, 5467, 12, 2345, 9852]));
// 输出: [12, 23, 345, 2345, 5467, 9852]关键点说明
- 稳定性：基数排序是稳定排序，相同数字的相对位置不变。
- 负数处理：当前实现未处理负数，可通过分离正负数并分别排序后合并。
- 字符串支持：可修改为支持字符串排序，按字符ASCII码分配桶。
性能优化建议
- 对于大型数据集，可考虑使用更高效的桶分配方式。
- 如果数字范围已知且较小，可提前设置最大位数减少计算。
