基数排序 Radix Sort

非比较排序 · 按位一轮轮排

什么是基数排序

计数排序适合小值域，可数字一大（比如三位数）桶就爆了。基数排序的巧思是按位处理：先只看个位把数分到 0~9 十个桶再收集，接着看十位、再百位……每一位都用一次稳定的分配收集。因为每轮都稳定，靠后处理的高位「盖过」低位，几轮下来整体就有序了——只用 10 个桶，就排好了任意位数的整数。

它怎么做

LSD（从最低位起）：第 d 轮，按每个数的第 d 位数字（0~9）分配到 10 个桶，再按桶 0→9 顺序收集回数组，作为下一轮的输入。点「下一步」看 [42, 7, 25, 63, 18, 31, 56, 9]：桶轨显示当前位的 0~9 分布，先按个位收集成一个序列，再按十位收集——第二轮结束就完全有序。

第 1 轮：按个位把 8 个数分配到 0–9 共 10 个桶

1function radixSort(a: number[]): number[] {
const maxVal = Math.max(...a);
const passes = String(maxVal).length;
for (let d = 0; d < passes; d++) {
  const buckets: number[][] = Array.from({ length: 10 }, () => []);
  const div = 10 ** d;
  for (const x of a) buckets[Math.floor(x / div) % 10].push(x);
  let w = 0;
  for (const bucket of buckets)
    for (const x of bucket) a[w++] = x;
}
return a;
13}

轮1/2

位个位

阶段开始

1 / 35

复杂度与适用

时间 O(d·(n + k))（d 位、每位 k=10 个桶）、额外空间 O(n + k)、稳定。当位数 d 远小于 log n 时，它比 O(n log n) 的比较排序更快——常用于定长整数、定长字符串、日期等键。前提是「每轮分配必须稳定」，否则低位的排序结果会被打乱。

每轮的桶 = 一次计数排序：基数排序本质是「对每一位做稳定计数排序」。
三种非比较排序：计数（桶=单个值）、基数（桶=一位数字 0-9，多轮）、桶排序（桶=一段值域）。

建议先看计数排序理解「稳定分配收集」，再回来体会基数怎么用它逐位攻克大值域；桶排序则是另一种分桶粒度。三页构成非比较线性排序的完整拼图。

算法可视化

基数排序 Radix Sort

什么是基数排序

它怎么做

复杂度与适用