第19课 - 基数排序 (Radix Sort)

课程名称：数据结构与算法
所属模块：排序算法
难度：中级
标签：radix-sort, digit, bucket
前序知识：计数排序、数组基础
下一课：桶排序

1. 学习目标

完成本课学习后，你将能够：

理解基数排序的核心思想：按位（从低位到高位或相反）进行多轮排序。
掌握基数排序（LSD）的完整实现步骤。
分析基数排序的时间复杂度与空间复杂度。
明确基数排序与其他线性时间排序算法（如计数排序、桶排序）的异同与适用场景。
能够运用基数排序解决实际的整数排序问题。

2. 核心概念

基数排序是什么？

想象一下，你要给一叠标有数字的卡片排序。一种高效的方法是：先按个位数字将它们分成0-9十堆，按顺序收集起来；然后按十位数字重复这个过程；接着是百位……直到处理完最大的数字的位数。这样，所有卡片自然就排好序了。这就是基数排序。

它是一种非比较排序算法，不通过元素间的直接比较来决定顺序，而是通过分配和收集的过程，基于整数的每一位（或字符的每一位）进行排序。

两种主要模式

LSD (Least Significant Digit first)：从最低位（个位）开始，逐轮向高位进行排序。这是最常用的方式，尤其适用于整数和定长字符串。
MSD (Most Significant Digit first)：从最高位开始，递归地对每个子序列的下一位进行排序。逻辑更复杂，但适用于可变长字符串（如字典序排序）。

本课将重点讲解 LSD 基数排序。

核心要求：稳定性是关键

在每一轮按某一位数字排序时，我们必须使用一种稳定的排序算法。为什么呢？因为当我们排好十位后，再排个位时，不能打乱已经由更高位建立起来的顺序。例如，数字 12 和 13，十位都是 1，在十位轮次中它们可能是相邻的。在个位轮次中，2 和 3 的排序必须保持它们原有的相对顺序（即12必须在13前面）。

最常用的稳定排序子程序是计数排序（我们上一课学习的内容）。它的实现简单，且本身就是稳定的，非常适合作为基数排序的“内循环”。

算法流程 (LSD)

找到待排序数组中的最大值，确定其位数（即需要进行多少轮排序）。
从个位（exp=1）开始，直到最高位（exp<=max）：
- 对数组中的所有元素，根据当前位（exp）的数字，执行一次稳定的计数排序。
- 将计数排序的结果更新回原数组。
所有轮次结束后，数组即为有序。

3. 代码示例

下面是一个完整的、可运行的 Python 基数排序（LSD）实现。

def counting_sort_for_radix(arr, exp):
    """
    为基数排序定制的计数排序子函数。
    arr: 待排序数组
    exp: 当前处理的位数因子 (1 代表个位, 10 代表十位, ...)
    """
    n = len(arr)
    output = [0] * n  # 存储排序后的数组
    count = [0] * 10  # 计数数组，0-9 对应每一位的数字

    # 1. 计数：统计当前位（exp）上每个数字（0-9）出现的次数
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # 2. 累加：修改 count 数组，使其表示当前位置之前的元素累计总数
    # 这一步是计数排序稳定性的关键，它决定了相同数字元素在输出中的相对顺序。
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 3. 构建输出数组：从后往前遍历原数组，以保持稳定性
    # (从后往前可以确保先出现的元素在输出中也靠前)
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    # 4. 将排序后的结果复制回原数组
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    """
    基数排序主函数 (LSD)
    """
    if not arr:
        return arr
    
    # 找到最大值，以确定最大位数
    max_val = max(arr)

    # 从个位开始，对每一位进行计数排序
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10  # 处理下一位 (10, 100, 1000, ...)

    return arr

# 测试代码
if __name__ == "__main__":
    data = [170, 45, 75, 90, 802, 2, 24, 66]
    print("原始数组:", data)
    
    sorted_data = radix_sort(data.copy()) # 使用副本避免修改原数据
    print("排序后数组:", sorted_data)
    
    # 更多测试用例
    test_cases = [
        [1, 1, 1, 1],
        [5, 4, 3, 2, 1],
        [123, 321, 213, 132, 312, 231],
        []  # 空数组
    ]
    
    for tc in test_cases:
        print(f"原始: {tc}, 排序后: {radix_sort(tc.copy())}")

预期输出：

原始数组: [170, 45, 75, 90, 802, 2, 24, 66]
排序后数组: [2, 24, 45, 66, 75, 90, 170, 802]
原始: [1, 1, 1, 1], 排序后: [1, 1, 1, 1]
原始: [5, 4, 3, 2, 1], 排序后: [1, 2, 3, 4, 5]
原始: [123, 321, 213, 132, 312, 231], 排序后: [123, 132, 213, 231, 312, 321]
原始: [], 排序后: []

4. 实践练习

练习 1：手动模拟

对于数组 [329, 457, 657, 839, 436, 720, 355]，请手动模拟 LSD 基数排序的前两轮（个位、十位）的过程，写出每轮计数排序后数组的状态。

练习 2：代码改进

当前的代码只支持十进制（基数为10）。请修改 counting_sort_for_radix 函数和 radix_sort 函数，使其能够支持任意基数 (base, b)。例如，base=8 (八进制) 或 base=16 (十六进制)。

提示：将计数数组的大小改为 base，计算每一位数字的方法改为 (arr[i] // exp) % base，累加循环和构建输出的范围也要相应改变。
测试：用 base=8 排序数组 [100, 64, 8, 512, 256] (这些数的八进制表示分别为 144, 100, 10, 1000, 400)。

练习 3：对比分析

分别用基数排序和内置排序算法（如 Python 的 sorted() 或 list.sort()）对一个包含 10 万个随机 6 位整数的列表进行排序，并比较两者的时间。

提示：使用 timeit 模块或 time.perf_counter() 来测量时间。
思考：在你的实验环境中，哪种方法更快？为什么？（考虑基数排序的时间复杂度 O(d*(n+k)) 和内置排序的复杂度 O(n log n)）。

5. 常见错误

忘记使用稳定的子排序算法：这是最致命的错误。如果使用不稳定的排序（如快速排序的分区过程）来处理某一位，那么在后续轮次中，先前排好的高位顺序会被打乱，导致最终结果错误。
混淆“位数”和“数字”：在提取某一位数字时，公式 (arr[i] // exp) % 10 容易出错。要确保 exp 是 1, 10, 100, ...，而不是 0, 1, 2, ...。
未正确处理不同长度的数字：LSD 基数排序通过从低位到高位的多次遍历自然地解决了这个问题。例如，数字 2 和 100，在个位轮，2 被视为 002（十位和百位为0），100 被视为 100。算法会正确地将 2 排在 100 前面，因为比较是从高位到低位进行的（最终比较的是百位的0和1）。
效率陷阱：当数字的位数 (d) 非常大时（例如，接近 n 或 log n），基数排序的效率会退化。因为总时间复杂度是 O(d * (n + k))。如果 d 是 O(log n)，则整体为 O(n log n)，与比较排序无异。如果 d 很大，则可能更慢。

6. 小结

核心思想：基数排序是一种非比较排序，通过按数字的每一位进行多轮稳定的排序（通常是计数排序）来完成整体排序。
主要流程：LSD（最低位优先）模式下，从个位开始，逐轮向高位排序。每轮都使用一个稳定的排序算法（如计数排序）。
时间复杂度：O(d * (n + k))。其中 d 是最大数字的位数，n 是元素个数，k 是基数（通常为10）。当 d 为常数且 k 与 n 同阶时，可近似为 O(n)。
空间复杂度：O(n + k)。主要空间开销来自计数排序中使用的辅助数组（大小为 k）和输出数组（大小为 n）。
关键特性：稳定、非比较、非原地（需要额外空间）。
适用场景：当待排序的元素是整数或可以表示为固定长度的字符串，且位数 d 不大时，基数排序非常高效。它常用于对大量整数进行排序，特别是在 n 很大但数字范围有限（即 d 很小）的情况下。

下一课预告：我们将学习另一种非比较排序——桶排序 (Bucket Sort)。它适用于数据分布均匀的场景，我们将探讨它与基数排序的异同。

练习编辑器

rust