🧮 基数排序 (Radix Sort)

难度 / Difficulty: 中等 (Medium)
分类 / Category: 非比较排序 (Non-comparison Sort)
时间复杂度 / Time Complexity: O(d × (n + k))
空间复杂度 / Space Complexity: O(n + k)

📖 算法简介 / Introduction

基数排序是一种非比较排序算法，按位数逐个进行排序。从最低位开始，按当前位将数据分配到 0-9 共 10 个桶中，收集后再按下一位排序，直到最高位完成。

Radix sort is a non-comparison sorting algorithm that sorts by each digit. Starting from the least significant digit (LSD), distribute elements into 10 buckets (0-9), collect them, then move to the next digit. Repeat until the most significant digit.

核心思想：“按位分组，逐步进位” — 把一个数字的每一位单独排序，最终得到完整有序的结果。

💡 算法原理 / Principle

两种方式

• LSD（最低位优先）：从低位到高位，如 1→10→100 依次排序
• MSD（最高位优先）：从高位到低位，更符合直觉但实现更复杂

LSD 流程

1. 找到最大值，确定位数 d
2. 从最低位开始，对每一位执行：
   • 按当前位值将元素分配到 0-9 桶中
   • 按桶顺序收集所有元素
3. 重复 d 次后，数组有序

📝 代码实现 / Implementation

from collections import deque

def radix_sort(arr):
    if not arr:
        return arr
    
    # 1. 找到最大值，确定位数
    max_val = max(arr)
    max_digits = len(str(max_val))
    
    # 2. 初始化 10 个桶
    buckets = [deque() for _ in range(10)]
    
    # 3. 从低位到高位排序
    exp = 1  # 当前位数（1=个位，10=十位，100=百位）
    for _ in range(max_digits):
        # 分配到桶
        for num in arr:
            digit = (num // exp) % 10
            buckets[digit].append(num)
        
        # 从桶中收集
        arr.clear()
        for bucket in buckets:
            while bucket:
                arr.append(bucket.popleft())
        
        # 处理下一位
        exp *= 10
    
    return arr

✨ 示例 / Example

输入数组：[170, 45, 75, 90, 802, 24, 2, 66]

Step 1: 按个位排序 (exp=1)
桶0: [170, 90]
桶2: [802, 2]
桶4: [24]
桶5: [45, 75]
桶6: [66]
收集后：[170, 90, 802, 2, 24, 45, 75, 66]

Step 2: 按十位排序 (exp=10)
桶0: [802, 2]
桶2: [24]
桶4: [45]
桶6: [66]
桶7: [170, 75]
桶9: [90]
收集后：[802, 2, 24, 45, 66, 170, 75, 90]

Step 3: 按百位排序 (exp=100)
桶0: [2, 24, 45, 66, 75, 90]
桶1: [170]
桶8: [802]
收集后：[2, 24, 45, 66, 75, 90, 170, 802]

最终输出：[2, 24, 45, 66, 75, 90, 170, 802]

🎯 适用场景 / Scenarios

• 整数排序 — 特别是范围不大的正整数
• 位数不多 — 如学号、工号、日期等固定位数的数据
• 需要稳定排序 — LSD 基数排序是稳定的
• 与其他 O(n log n) 排序对比 — 当位数 d 较小时有优势

Integer sorting with bounded digits, Student IDs, Employee numbers, Dates, When digit count d is small relative to n.

⚠️ 优缺点 / Pros & Cons

🔄 与计数排序对比 / Comparison