基数排序Radix sort

按数位分轮排序，逐步组合各位的顺序。

核心约束: LSD 方案每轮需稳定地保留已处理低位的次序。
适用问题: 定长整数、可按位拆解的键。
边界与取舍: 键表示、符号处理、基数和缓存开销影响实现。

时间与空间#

n 为元素数，d 为处理位数，k 为每位基数。

时间复杂度: LSD 计数排序实现 $O(d(n+k))$
辅助空间: $O(n+k)$

每轮必须稳定，取一位的成本为 $O(1)$ 。负数、变长字符串和 Unicode 排序规则需单独编码；MSD 与比较排序混合实现有不同条件。

基础原理参考资料

MIT 6.006 · Linear Sorting元组排序、稳定分位排序与基数选择。

Princeton · LSD定长字符串和整数的低位优先基数排序实现。