排序算法系列 11：基数排序——一位一位地排，最后自然有序

基数排序是非比较排序里最精巧的一个。它的思路是：不看整个数字大小，而是一位一位地看——先按个位排，再按十位排，再按百位排。排完所有位之后，整体就有序了。

听起来有点反直觉：只看一位怎么能排好整体？关键在于一个前提——每一轮排序必须是稳定的。

核心思想

用 [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

搞定。

为什么每轮必须稳定？

假设你按十位排完之后，45 排在 66 前面（因为十位 4 < 6）。

接下来按百位排的时候，45 和 66 百位都是 0，会被分到同一个桶里。如果这一轮排序不稳定，45 和 66 的相对顺序可能被打乱。但它们在上一轮按十位已经排好了——打乱就错了。

所以基数排序的每一轮必须用稳定排序。计数排序（稳定版）刚好适合——每一位只有 0~9 十种值，范围极小。

代码实现

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

  let result = [...arr];
  const max = Math.max(...result);

  // 从个位开始，逐位排序
  for (let digit = 1; Math.floor(max / digit) > 0; digit *= 10) {
    result = countingSortByDigit(result, digit);
  }

  return result;
}

function countingSortByDigit(arr, digit) {
  const count = new Array(10).fill(0);
  const output = new Array(arr.length);

  // 统计当前位的各数字出现次数
  for (const num of arr) {
    const bucket = Math.floor(num / digit) % 10;
    count[bucket]++;
  }

  // 前缀和
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  // 从后往前放，保持稳定性
  for (let i = arr.length - 1; i >= 0; i--) {
    const bucket = Math.floor(arr[i] / digit) % 10;
    count[bucket]--;
    output[count[bucket]] = arr[i];
  }

  return output;
}

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

countingSortByDigit 就是上一篇计数排序的稳定版本，只是 key 变成了"当前位上的数字"。

Math.floor(num / digit) % 10 取的就是某一位上的值：

• digit = 1 取个位
• digit = 10 取十位
• digit = 100 取百位

LSD vs MSD

上面的实现是 LSD（Least Significant Digit）——从最低位开始排。

还有一种 MSD（Most Significant Digit）——从最高位开始排。MSD 需要递归处理子桶，实现更复杂，一般入门只需要掌握 LSD。

LSD 的逻辑更直觉：低位排完的顺序，在高位排序时被"保护"（因为稳定性），最终高位决定整体大小关系。

复杂度

设 n 是数据量，d 是最大位数，k 是每位的基数（十进制是 10）：

因为 k = 10 是常数，可以简化理解为 O(d × n)。如果位数 d 有限（比如最多 6 位数），这基本就是线性的。

稳定性：稳定（前提是每一轮用了稳定排序）。

适用场景

• 非负整数排序
• 编号排序（工号、订单号）
• 固定长度字符串排序
• 手机号后几位排序

不适合：

• 浮点数（需要额外转换）
• 负数（需要特殊处理）
• 位数差异很大的数据（短的要补零）

和计数排序、桶排序的关系

三个非比较排序各有侧重：

基数排序可以看成"对每一位做计数排序，重复 d 次"。

写在最后

到这里，十大经典排序算法都讲完了。下一篇也是最后一篇，我们把所有排序算法放在一起做个横向对比——什么场景选什么算法，给出一个清晰的决策思路。

系列导航

上一篇：排序算法系列 10：桶排序——先分堆再各自整理

下一篇：排序算法系列 12：选型指南——到底该用哪个？