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

基数排序是一种非比较型整数排序算法，其核心思想是按照数字的每一位（从低位到高位或从高位到低位）进行多次排序，每次排序使用稳定的排序算法（如计数排序）。基数排序适用于整数或字符串的排序，时间复杂度为O(d*(n+k))，其中d是最大数字的位数，k是每一位的取值范围（如十进制数字为10）。

算法步骤

1. 确定最大数字的位数：遍历数组，找到最大值，计算其位数d。
2. 从最低位开始排序：使用稳定的排序算法（如计数排序）对数字的当前位进行排序。
3. 重复排序过程：对每一位（从低位到高位）重复步骤2，直到最高位排序完成。

详细实现（以十进制数字为例）

步骤1：实现计数排序（作为基数排序的子过程）

计数排序需要对当前位（如个位、十位）进行稳定排序：

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]

步骤2：实现基数排序

def radix_sort(arr):
    if not arr:
        return arr
    
    # 找到最大值，确定最大位数
    max_val = max(arr)
    exp = 1  # 从个位开始
    
    # 对每一位进行计数排序
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10  # 移动到更高位（十位、百位等）

示例说明

对数组 [170, 45, 75, 90, 2, 802, 24] 进行排序：

1. 按个位排序：
   • 个位数字：0, 5, 5, 0, 2, 2, 4
   • 排序后：[170, 90, 2, 802, 24, 45, 75]
2. 按十位排序：
   • 十位数字：7, 9, 0, 0, 2, 4, 7
   • 排序后：[2, 802, 24, 45, 75, 170, 90]
3. 按百位排序：
   • 百位数字：0, 8, 0, 0, 0, 1, 0
   • 排序后：[2, 24, 45, 75, 90, 170, 802]

关键点分析

1. 稳定性：基数排序依赖子排序算法的稳定性，否则高位排序会破坏低位排序的结果。
2. 时间复杂度：O(d*(n+k))，其中d为最大位数，k为基数（如10）。当d较小且k接近n时，效率较高。
3. 空间复杂度：O(n+k)，需要额外空间用于计数和输出数组。

应用场景

• 整数排序：尤其适用于位数较少的整数（如手机号、身份证号局部排序）。
• 字符串字典序排序：对每个字符的ASCII码进行基数排序。
• 非比较排序需求：当比较操作成本高时（如字符串比较），基数排序可能更高效。

扩展思考

• 高位优先（MSD）基数排序：从最高位开始排序，适合字符串排序，但需要递归处理子组。
• 负数处理：可通过偏移量将负数转换为正数（如加上最小负数的绝对值），排序后再转换回来。