手写基数排序（Radix Sort）及其应用场景

基数排序是一种非比较型整数排序算法，其核心思想是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。它通过多次分配和收集来实现排序，通常使用稳定排序算法（如计数排序）作为子排序过程。

算法步骤详解

1. 确定最大数字的位数

   • 首先遍历数组，找到最大值max
   • 计算max的位数d（如max=345，则d=3）

2. 从最低位到最高位依次排序

   • 使用稳定的排序算法（通常用计数排序）对每一位进行排序
   • 第1轮：按个位数排序
   • 第2轮：按十位数排序
   • ...
   • 第d轮：按最高位排序

3. 计数排序作为子过程

   • 创建大小为10的计数数组（0-9）
   • 统计每个数字在当前位的出现次数
   • 计算前缀和确定每个数字的最终位置
   • 从后往前遍历原数组，保持稳定性

4. 时间复杂度分析

   • 时间复杂度：O(d×(n+k))，其中d是最大位数，n是元素个数，k是基数（通常k=10）
   • 空间复杂度：O(n+k)

具体实现示例（Python）

def radix_sort(arr):
    if not arr:
        return arr
    
    # 找到最大值确定位数
    max_val = max(arr)
    exp = 1  # 当前位数（1表示个位）
    
    while max_val // exp > 0:
        # 使用计数排序对当前位排序
        counting_sort_for_radix(arr, exp)
        exp *= 10  # 移动到下一位
    
    return arr

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n  # 输出数组
    count = [0] * 10  # 计数数组（0-9）
    
    # 统计每个数字的出现次数
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    
    # 计算前缀和
    for i in range(1, 10):
        count[i] += count[i-1]
    
    # 从后往前遍历，保持稳定性
    for i in range(n-1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index]-1] = arr[i]
        count[index] -= 1
    
    # 将排序结果复制回原数组
    for i in range(n):
        arr[i] = output[i]

应用场景分析

1. 整数排序场景

   • 适合排序非负整数
   • 对于有负整数的情况，需要预处理（如加上偏移量）

2. 数据范围有限但数量大

   • 当数字位数d相对较小，而n很大时效率高
   • 例如：手机号排序、身份证号排序

3. 字符串排序

   • 可以对等长字符串按字典序排序
   • 从最后一个字符开始向前排序

4. 特定领域应用

   • 计算机图形学中的坐标排序
   • 数据库中的多关键字排序

优缺点总结

优点：

• 时间复杂度稳定为O(dn)
• 不需要比较操作
• 稳定性好

缺点：

• 需要额外空间
• 对数据特征敏感（依赖位数d）
• 不适用于浮点数排序

基数排序在特定场景下非常高效，特别是当数字位数不大且数据量较大时，其性能优于比较排序算法。