基数排序

问题

实现基数排序算法，对非负整数数组进行排序。

解答

基数排序是一种非比较排序算法，按照数字的每一位进行排序，从最低位到最高位依次处理。

function radixSort(arr) {
  if (arr.length <= 1) return arr;

  // 找到最大值，确定最大位数
  const max = Math.max(...arr);
  const maxDigits = String(max).length;

  let result = [...arr];

  // 从个位开始，逐位排序
  for (let digit = 0; digit < maxDigits; digit++) {
    // 创建 10 个桶（0-9）
    const buckets = Array.from({ length: 10 }, () => []);

    // 将数字放入对应的桶
    for (const num of result) {
      // 获取当前位的数字
      const digitValue = Math.floor(num / Math.pow(10, digit)) % 10;
      buckets[digitValue].push(num);
    }

    // 按桶的顺序收集数字
    result = buckets.flat();
  }

  return result;
}

// 测试
console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]));
// [2, 24, 45, 66, 75, 90, 170, 802]

支持负数的版本

function radixSortWithNegative(arr) {
  if (arr.length <= 1) return arr;

  // 分离正数和负数
  const negative = arr.filter(n => n < 0).map(n => -n);
  const positive = arr.filter(n => n >= 0);

  // 分别排序
  const sortedNegative = radixSort(negative).reverse().map(n => -n);
  const sortedPositive = radixSort(positive);

  // 合并：负数在前，正数在后
  return [...sortedNegative, ...sortedPositive];
}

// 测试
console.log(radixSortWithNegative([170, -45, 75, -90, 802, 24, -2, 66]));
// [-90, -45, -2, 24, 66, 75, 170, 802]

排序过程演示

// 以 [170, 45, 75, 90, 802, 24, 2, 66] 为例

// 第一轮：按个位排序
// 桶 0: [170, 90]
// 桶 2: [802, 2]
// 桶 4: [24]
// 桶 5: [45, 75]
// 桶 6: [66]
// 结果: [170, 90, 802, 2, 24, 45, 75, 66]

// 第二轮：按十位排序
// 桶 0: [802, 2]
// 桶 2: [24]
// 桶 4: [45]
// 桶 6: [66]
// 桶 7: [170, 75]
// 桶 9: [90]
// 结果: [802, 2, 24, 45, 66, 170, 75, 90]

// 第三轮：按百位排序
// 桶 0: [2, 24, 45, 66, 75, 90]
// 桶 1: [170]
// 桶 8: [802]
// 结果: [2, 24, 45, 66, 75, 90, 170, 802]

关键点

• 非比较排序：不通过元素间比较，而是按位分配到桶中
• 时间复杂度 O(d × n)：d 是最大位数，n 是元素个数
• 空间复杂度 O(n + k)：k 是桶的数量（10 个）
• 稳定排序：相同值的元素保持原有相对顺序
• 适用场景：整数排序，位数较少时效率高于比较排序