基数排序适用于"关键字可以表示为若干位"的数据，例如十进制整数、字符串或固定长度字串。它通常采用 LSD（Least Significant Digit，最低位优先）策略：

1. 先按最低位分配到桶里；
2. 再按桶序收集；
3. 继续处理更高位，直到最高位。

Ph1zの理解： 基数排序就像按学号排队——先看最后一位，按最后一位排好；再看倒数第二位，按倒数第二位排好（但保持最后一位的顺序不变）；……最后看第一位。因为每次都是稳定排序，高位排序不会打乱低位已经排好的顺序，所以最终一定正确。这叫"LSD（最低位优先）"——先排低位，后排高位。

代码

void radixSort(int a[], int n) {
    int maxVal = *max_element(a, a + n);
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSortByDigit(a, n, exp);  // 稳定计数排序按当前位分配
    }
}

正确性证明

基数排序的有效性来自"稳定性 + 位级排序"。

• 对当前位做一次稳定排序；
• 稳定排序意味着较高位相同的元素，低位排序结果不会打乱它们的相对顺序；
• 处理完最低位后，数值按最低位有序；
• 再按次低位稳定排序，确保次低位优先于更高位的比较关系被正确保留；
• 最终所有位都处理完成后，整个关键字顺序就正确了。

为什么必须稳定？ 假设当前排十位，两个数的十位相同但个位不同（如 23 和 27）。如果排序不稳定，27 可能排到 23 前面——个位的排序白做了。稳定性保证了"低位辛辛苦苦排好的顺序，高位排序不会搞乱"。

因此，若每一位排序都稳定，那么整个基数排序正确。 ✓

复杂度分析

若关键字有 $d$ 位，每位基数为 $r$，则每一趟的分配/收集为 $O(n+r)$，总复杂度：

$$T(n)=O(d(n+r)).$$

若 $d$ 与 $r$ 是常数（如 32 位整数按字节分解：$d=4,r=256$），则可看作线性时间 $O(n)$。

空间复杂度： $O(n+r)$。

稳定性： 稳定（前提是每一位的排序都稳定）。

基数排序 vs 比较排序： 基数排序不是"比较排序"——它不依赖"两个元素之间必须比较大小"，它依赖"按位检查"。所以它不违背比较排序的 $\mathrm{\Omega }(n\log n)$ 下界；它只是使用了更强的输入结构信息（关键字可以按位分解）。就像考试不能带计算器（比较排序），但如果你自己心算能力够强（非比较排序），算得比别人快不犯规喵