手写算法并记住它：基数排序

一、基数排序的核心原理

基数排序（Radix Sort）是一种非比较型整数排序算法，其核心思想是”分而治之”与”按位处理”。不同于传统排序算法通过比较元素大小决定顺序，基数排序通过逐位分配和收集实现排序。这种策略尤其适合处理固定位数的整数或字符串数据。

1.1 排序的数学基础

假设待排序数组包含n个d位数，每个数字的位数范围是0-9。基数排序通过从最低位（LSD）到最高位（MSD）依次处理每个数字位，将数据分配到10个桶中（对应0-9），再按顺序收集形成新序列。这个过程重复d次即可完成排序。

数学证明表明，当数字位数固定时，基数排序的时间复杂度为O(d*(n+k))，其中k是基数（通常为10）。在数字位数d与log₂n同阶时，其效率优于O(nlogn)的比较排序算法。

1.2 LSD与MSD策略对比

• LSD（最低位优先）：从个位开始处理，每次分配后保持原始顺序。实现简单，适合数字位数已知的场景。
• MSD（最高位优先）：从最高位开始处理，需要递归处理子数组。适合处理变长字符串或前缀匹配场景。

二、手写实现LSD基数排序

2.1 基础代码框架

def radix_sort_lsd(arr):
    # 获取最大数字的位数
    max_num = max(arr)
    max_digit = len(str(max_num))
    for digit in range(max_digit):
        # 初始化10个桶
        buckets = [[] for _ in range(10)]
        # 分配阶段
        for num in arr:
            # 获取当前位的数字
            current_digit = (num // (10 ** digit)) % 10
            buckets[current_digit].append(num)
        # 收集阶段
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
    return arr

2.2 关键实现细节

1. 位数计算优化：使用max_digit = len(str(max_num))快速获取最大位数，但需注意负数处理。
2. 桶分配公式：(num // (10 ** digit)) % 10精确提取指定位的数字。
3. 稳定性保证：按桶顺序收集保证相同数字的原始顺序。

2.3 边界条件处理

• 负数处理：需分离正负数，分别排序后合并。
• 零填充：不同位数数字比较时，短数字前补零（如12视为012）。
• 空数组检查：函数开始时检查if not arr: return []。

三、MSD基数排序的实现与优化

3.1 递归实现框架

def radix_sort_msd(arr):
    if len(arr) <= 1:
        return arr
    # 获取最高位数字
    max_num = max(arr)
    max_digit = len(str(max_num))
    digit = max_digit - 1
    buckets = [[] for _ in range(10)]
    for num in arr:
        current_digit = (num // (10 ** digit)) % 10
        buckets[current_digit].append(num)
    # 递归处理每个桶
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(radix_sort_msd(bucket))
    return sorted_arr

3.2 性能优化技巧

1. 小数组切换：当子数组长度小于阈值（如20）时，切换为插入排序。
2. 内存优化：使用原地分配技术减少空间复杂度。
3. 并行处理：对独立桶进行并行排序（需线程安全）。

四、时间复杂度深度分析

4.1 最佳/最差情况

• 最佳情况：所有数字位数相同且分布均匀，时间复杂度O(dn)。
• 最差情况：数字位数差异大或分布集中，仍为O(dn)但常数因子增大。

4.2 与比较排序的对比

当d=O(logn)时，基数排序优于O(nlogn)的比较排序。例如对32位整数，d=10（考虑符号位），基数排序效率更高。

五、实际应用场景与代码示例

5.1 典型应用场景

1. 信用卡号排序：固定16位数字，LSD实现高效。
2. IP地址排序：转换为整数后使用基数排序。
3. 日期排序：将YYYYMMDD格式视为整数排序。

5.2 完整实现示例（含负数处理）

def radix_sort_complete(arr):
    if not arr:
        return []
    # 分离正负数
    negatives = [x for x in arr if x < 0]
    positives = [x for x in arr if x >= 0]
    # 处理负数（取绝对值后排序，再反转并取负）
    if negatives:
        max_abs = max(abs(x) for x in negatives)
        max_digit = len(str(max_abs))
        for digit in range(max_digit):
            buckets = [[] for _ in range(10)]
            for num in negatives:
                abs_num = abs(num)
                current_digit = (abs_num // (10 ** digit)) % 10
                buckets[current_digit].append(num)
            negatives = []
            for bucket in reversed(buckets):  # 负数需要反转桶顺序
                negatives.extend(bucket)
    # 处理正数
    if positives:
        max_num = max(positives)
        max_digit = len(str(max_num))
        for digit in range(max_digit):
            buckets = [[] for _ in range(10)]
            for num in positives:
                current_digit = (num // (10 ** digit)) % 10
                buckets[current_digit].append(num)
            positives = []
            for bucket in buckets:
                positives.extend(bucket)
    return negatives + positives

六、记忆与实践技巧

1. 可视化练习：用纸笔模拟4-5位数字的排序过程。
2. 调试技巧：在分配阶段打印桶内容，验证分配正确性。
3. 变体掌握：尝试实现字符串基数排序（按字符ASCII码分配）。

七、常见误区与解决方案

1. 位数计算错误：使用math.log10可能产生浮点误差，推荐字符串转换法。
2. 稳定性问题：确保收集阶段按桶顺序，而非随机顺序。
3. 内存爆炸：对大规模数据，使用外部排序技术分块处理。

通过系统化的手写实践与理论验证，开发者不仅能深入理解基数排序的精髓，更能培养解决复杂排序问题的能力。建议结合LeetCode相关题目（如164.最大间距）进行实战演练，巩固算法思维。