基数排序

基数排序如何工作？

• 原理: 在计数排序的基础上, 按数字各位从低位到高位依次排序;
• 第 k 轮只关注第 k 位, 用计数排序把元素按该位聚集;
• 低位排完后, 高位排序不会打乱低位已经确定的相对次序;
• 处理完最高位后数组整体有序;

如何取数字的第 k 位？

• 用 exp = 10^(k-1) 代替位数 k, 避免重复计算次方;
• 取位公式: digit = floor(num / exp) % 10;

基数排序如何实现？

function radixSort(nums: number[]): void {
  const m = Math.max(...nums);
  for (let exp = 1; exp <= m; exp *= 10) {
    countingSortDigit(nums, exp);
  }
}

// 按第 k 位 (exp = 10^(k-1)) 做计数排序
function countingSortDigit(nums: number[], exp: number): void {
  const counter = new Array(10).fill(0);
  for (const num of nums) counter[Math.floor(num / exp) % 10]++;
  for (let i = 1; i < 10; i++) counter[i] += counter[i - 1];
  const res = new Array(nums.length).fill(0);
  for (let i = nums.length - 1; i >= 0; i--) {
    const d = Math.floor(nums[i] / exp) % 10;
    res[--counter[d]] = nums[i];
  }
  for (let i = 0; i < nums.length; i++) nums[i] = res[i];
}

基数排序的特性是什么？

• 时间复杂度: O(nk), k 为最大位数;
• 空间复杂度: O(n + d), d 为基数 (十进制为 10);
• 稳定性: 稳定排序, 每一位都依赖计数排序的稳定性;
• 适用场景: 数据范围大但位数不多;
• 限制: 上述实现只处理非负整数;