js实现基数算法
基数排序（Radix Sort）简介
基数排序是一种非比较型整数排序算法，通过逐位分配和收集实现排序。适用于整数或固定格式字符串，时间复杂度为O(nk)，其中n是元素数量，k是数字位数。
实现基数排序的步骤
确定最大数字位数
找出数组中最大数字的位数，确定需要进行多少轮排序。例如，数组[3, 1, 44, 12]的最大数字是44，有2位。
function getMaxDigit(arr) {
let max = Math.max(...arr);
return String(max).length;
}按位排序（从低位到高位） 使用计数排序对每一位进行稳定排序。创建10个桶（0-9），根据当前位的数字将元素分配到对应桶中，再按顺序收集回原数组。
function radixSort(arr) {
const maxDigit = getMaxDigit(arr);
let buckets = Array.from({ length: 10 }, () => []);
for (let i = 0; i < maxDigit; i++) {
// 分配
for (let num of arr) {
const digit = getDigit(num, i);
buckets[digit].push(num);
}
// 收集
arr = [].concat(...buckets);
buckets = Array.from({ length: 10 }, () => []);
}
return arr;
}
function getDigit(num, place) {
return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}处理负数的情况
若数组包含负数，可先分离正负数，分别排序后合并。负数需取绝对值并按高位到低位排序，最后反转结果。
function radixSortWithNegative(arr) {
const positives = arr.filter(num => num >= 0);
const negatives = arr.filter(num => num < 0).map(num => -num);
const sortedPositives = radixSort(positives);
const sortedNegatives = radixSort(negatives).reverse().map(num => -num);
return [...sortedNegatives, ...sortedPositives];
}示例测试
console.log(radixSort([3, 1, 44, 12])); // [1, 3, 12, 44]
console.log(radixSortWithNegative([-3, 1, -44, 12])); // [-44, -3, 1, 12]注意事项
- 基数排序对数据格式要求严格，需确保所有元素位数相同或能补齐。
- 对于浮点数，需转换为整数处理（如乘以10的幂次），排序后再转换回去。
