基数排序详解：原理、代码与时间复杂度

基数排序解决什么问题

计数排序是线性的，但需要一个与整个键范围一样大的计数数组，这对 32 位或 64 位整数来说不可能。基数排序把每个键拆成小的数位，每位运行一次计数排序，因此每一趟的计数数组只需 b 项（十进制位是 10，字节是 256）。

它适用于任何能拆成固定长度的小符号序列的键：非负整数、写成 YYYYMMDD 的日期、邮政编码这类定长编码、IP 地址以及定宽字符串。

示例：十进制的 LSD 基数排序

对 [170, 45, 75, 90, 802, 24, 2, 66] 排序。最大的数有 3 位，所以共 3 趟。每一趟都是按一位数字做的稳定排序：数位相同的元素保持上一趟的顺序。

第 2 趟之后，数字已按末两位有序。在第 3 趟中，2、24、45、66、75 和 90 的百位都是 0，稳定性使它们保持第 2 趟产生的顺序。这就是每一趟都必须稳定的原因。

Python 实现

def counting_pass(nums, exp, base):
    """Stable counting sort of nums by the digit at exp."""
    count = [0] * base
    for x in nums:
        count[(x // exp) % base] += 1
    for d in range(1, base):
        count[d] += count[d - 1]
    out = [0] * len(nums)
    for x in reversed(nums):
        d = (x // exp) % base
        count[d] -= 1
        out[count[d]] = x
    return out

def radix_sort(nums, base=10):
    """LSD radix sort for non-negative integers."""
    if not nums:
        return []
    exp, biggest = 1, max(nums)
    while biggest // exp > 0:
        nums = counting_pass(nums, exp, base)
        exp *= base
    return nums

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
print(radix_sort([3, 0, 1, 0], base=256))   # [0, 0, 1, 3]

以 256 为基数，意味着每一趟查看一个字节，所以 32 位整数只需 4 趟。要包含负数，可以把负数和非负数分开排序再拼接，或者把所有键偏移最小值。对于定长字符串，把位置 i 处的字符编码当作数位，从最后一个位置向第一个位置逐位处理。

时间与空间复杂度

当 d 是常数（定宽键）且 b 取接近 n 或固定值（如 256）时，时间是 O(n)。对 n 个互不相同的键，d 至少为 log_b n，所以对任意大小的键，基数排序并不能突破 O(n log n)；它之所以快，是因为每一步都只是简单的数组操作。

基数排序与其他排序算法的比较

表中 n 是键的个数，k 是计数排序的键范围，d 是位数，b 是基数。只要每一位的排序趟都是稳定的，LSD 基数排序就是稳定的。它要求键具有固定的结构，而归并排序和快速排序这类比较排序适用于任何顺序，包括自定义的比较函数。

LSD 与 MSD，以及常见错误

何时使用基数排序

基数排序很适合对大量定宽整数或键排序，例如 32 位 ID、时间戳、IPv4 地址或定长字符串，尤其是在 GPU 和高性能库中，它规整的内存访问方式能带来收益。它被用于后缀数组构造，以及某些数据库和图形负载。对于普通的 Python 列表，sorted() 在实践中几乎总是更快，因为它运行的是优化过的 C 代码。面试中，被问到如何用线性时间排序时会谈到基数排序，例如「最大间距」（Maximum Gap）这道题。