基数排序的基本原理
基数排序的核心思路是将整数按位数拆分，从低位到高位依次进行排序。它不需要直接比较元素的大小，而是通过分配和收集的过程完成排序，通常借助桶结构来实现。对于十进制整数来说，每一位的取值都是0到9，因此我们可以准备10个桶，对应每一位的可能取值。
JavaScript实现基数排序的步骤
1. 获取数组中最大数的位数
基数排序需要从最低位到最高位依次处理，所以首先要知道数组中最大数的位数，确定需要循环的次数。我们可以通过不断除以10来计算位数，直到数字小于10为止。
2. 按位分配元素到桶中
从个位开始，依次取每个元素的当前位值，将元素放入对应编号的桶里。比如当前处理个位，元素123的个位是3，就把它放到编号为3的桶中。
3. 从桶中收集元素回到原数组
把所有桶中的元素按桶编号从小到大依次取出来，放回原数组，完成当前位的排序。然后处理下一位，直到所有位都处理完毕。
完整代码实现
下面是完整的JavaScript基数排序实现代码，包含详细的中文注释说明逻辑：
/**
* 基数排序函数
* @param {number[]} arr 待排序的整数数组
* @returns {number[]} 排序后的数组
*/
function radixSort(arr) {
if (!Array.isArray(arr) || arr.length <= 1) {
return arr;
}
// 获取最大数的位数
let maxNum = Math.max(...arr);
let maxDigit = 0;
while (maxNum > 0) {
maxDigit++;
maxNum = Math.floor(maxNum / 10);
}
// 初始化10个桶，对应0-9
let buckets = Array.from({ length: 10 }, () => []);
// 从个位开始，依次处理每一位
for (let i = 0; i < maxDigit; i++) {
// 遍历数组，将元素放入对应桶中
for (let num of arr) {
// 获取当前位的数值，i=0是个位，i=1是十位，以此类推
let digit = Math.floor(num / Math.pow(10, i)) % 10;
buckets[digit].push(num);
}
// 收集桶中的元素回到数组
let index = 0;
for (let bucket of buckets) {
for (let num of bucket) {
arr[index++] = num;
}
// 清空当前桶，准备下一次处理
bucket.length = 0;
}
}
return arr;
}
// 测试示例
let testArr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log("排序前：", testArr);
radixSort(testArr);
console.log("排序后：", testArr);复杂度与适用场景
基数排序的时间复杂度为O(k*n)，其中k是最大数的位数，n是数组长度。当处理大量整数且位数不多时，基数排序的效率很高。但它只适合整数排序，对于包含负数、浮点数的数组需要先做额外处理，也不适合非数值类型的排序场景。
注意事项
- 上述实现仅支持非负整数排序，如果需要处理负数，可以先将数组分为正数和负数两部分，分别排序后拼接。
- 如果数组中存在浮点数，需要先统一转换为整数处理，或者调整位数计算的逻辑适配小数位。
- 实际使用时可以根据数据特点调整桶的实现方式，比如数据量极大时可以考虑更高效的桶结构。
基数排序JavaScript算法实现排序算法修改时间：2026-06-05 01:55:11