基数排序（Radix Sort）

基数排序是一种非比较型整数排序算法，其核心思想是将整数按位数逐位排序，从最低有效位（LSB）到最高有效位（MSB）依次处理。基数排序通常使用稳定的排序算法（如计数排序）作为子程序来对每位进行排序。

1. 算法背景与适用场景

• 适用条件：仅适用于整数或可表示为整数的数据（如字符串、浮点数需转换）。
• 时间复杂度：O(d·(n + k))，其中d为最大位数，n为元素个数，k为基数（如十进制中k=10）。
• 空间复杂度：O(n + k)，需要额外空间存储临时排序结果。
• 优势：当d较小且k不大时，效率高于比较排序算法（如O(n log n)的快速排序）。

2. 算法步骤详解

基数排序分为以下步骤：

步骤1：确定最大位数

• 遍历数组，找到最大值，并计算其位数d。
  示例：数组[170, 45, 75, 90, 802, 24, 2, 66]中，最大值为802，位数为3。

步骤2：从最低位到最高位逐位排序

• 使用稳定的排序算法（通常为计数排序）对每一位进行排序。
  关键原理：高位数字的优先级高于低位，但必须从低位开始排序，以保证高位的排序不会破坏低位已确定的顺序。

步骤3：计数排序子过程（以十进制为例）

1. 创建计数数组：长度为10（十进制数字0-9），初始化为0。
2. 统计频率：遍历当前位，统计每个数字出现的次数。
3. 计算前缀和：将计数数组转换为位置索引（前缀和），表示每个数字在输出数组中的最后位置。
4. 生成排序结果：从原数组末尾向前遍历（保证稳定性），根据当前位数字和前缀和数组，将元素放入临时数组的正确位置。
5. 更新数组：将临时数组复制回原数组，完成当前位的排序。

步骤4：重复步骤2和3

• 对每一位重复排序，直到处理完最高位。

3. 示例演示

以数组[170, 45, 75, 90, 802, 24, 2, 66]为例：

• 第1轮（个位）：
  按个位数字排序：
  170(个位0), 90(0), 802(2), 2(2), 24(4), 45(5), 75(5), 66(6)
  结果：[170, 90, 802, 2, 24, 45, 75, 66]

• 第2轮（十位）：
  按十位数字排序（保持个位顺序）：
  802(十位0), 2(0), 24(2), 45(4), 66(6), 170(7), 75(7), 90(9)
  结果：[802, 2, 24, 45, 66, 170, 75, 90]

• 第3轮（百位）：
  按百位数字排序（保持十位和个位顺序）：
  2(百位0), 24(0), 45(0), 66(0), 75(0), 90(0), 170(1), 802(8)
  最终结果：[2, 24, 45, 66, 75, 90, 170, 802]

4. 关键注意事项

• 稳定性要求：子排序算法必须是稳定的，否则高位排序会打乱低位已排好的顺序。
• 负数处理：需将负数转换为正数（如加上偏移量）或单独处理符号位。
• 基数选择：可根据数据特性调整基数（如二进制基数k=2），减少位数d以提高效率。

5. 代码实现（伪代码）

function radixSort(arr):
    max_val = max(arr)
    exp = 1  // 从个位开始
    
    while max_val // exp > 0:
        countingSortForDigit(arr, exp)
        exp *= 10

function countingSortForDigit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  // 十进制0-9
    
    // 统计当前位数字出现次数
    for i in range(n):
        digit = (arr[i] // exp) % 10
        count[digit] += 1
    
    // 计算前缀和
    for i in range(1, 10):
        count[i] += count[i-1]
    
    // 从后向前遍历保证稳定性
    for i in range(n-1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
    
    // 复制回原数组
    for i in range(n):
        arr[i] = output[i]

6. 总结

基数排序通过逐位排序避免了直接比较，适用于整数排序且位数有限的场景。其效率依赖于位数d和基数k，在数据范围可控时（如手机号、身份证号排序）具有明显优势。