基数排序

基数排序（Radix Sort）是一种非比较型的整数排序算法，通过逐位分配和收集元素实现排序。其核心思想是将整数按位数切割成不同数字，然后按每个位数分别比较。基数排序适用于整数或字符串（按字典序）的排序，时间复杂度可达线性级（$O(nk)$，其中$n$为元素数量，$k$为最大位数）。

算法原理

基数排序分为以下步骤： 1. 确定最大位数：找到数组中最大数字的位数$d$。 2. 按位排序：从最低位（LSD，Least Significant Digit）或最高位（MSD，Most Significant Digit）开始，依次对每一位进行稳定排序（通常使用计数排序）。 3. 合并结果：每轮排序后，按当前位数重新排列数组，最终得到有序序列。

LSD vs MSD

• LSD（最低位优先）：从右向左逐位排序，适用于位数较少的整数。
• MSD（最高位优先）：从左向右递归排序，适用于字符串或位数差异大的数据。

算法步骤示例

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

1. 找到最大数802（3位数），补齐其他数字为3位：[170, 045, 075, 090, 802, 024, 002, 066]。 2. 按个位、十位、百位依次排序：

flowchart LR A[原始数组] --> B[按个位排序] B --> C[170, 090, 802, 002, 024, 045, 075, 066] C --> D[按十位排序] D --> E[802, 002, 024, 045, 066, 170, 075, 090] E --> F[按百位排序] F --> G[002, 024, 045, 066, 075, 090, 170, 802]

代码实现

以下是Python实现的基数排序（LSD版本）：

  
def radix_sort(arr):  
    # 获取最大位数  
    max_num = max(arr)  
    max_digit = len(str(max_num))  

    for digit in range(max_digit):  
        # 使用计数排序对当前位排序  
        count = [0] * 10  
        output = [0] * len(arr)  

        # 统计当前位数字出现次数  
        for num in arr:  
            current_digit = (num // (10 ** digit)) % 10  
            count[current_digit] += 1  

        # 计算累积分布  
        for i in range(1, 10):  
            count[i] += count[i - 1]  

        # 按当前位重新排列  
        for num in reversed(arr):  
            current_digit = (num // (10 ** digit)) % 10  
            output[count[current_digit] - 1] = num  
            count[current_digit] -= 1  

        arr = output.copy()  
    return arr  

# 示例  
input_arr = [170, 45, 75, 90, 802, 24, 2, 66]  
print("输入数组:", input_arr)  
sorted_arr = radix_sort(input_arr)  
print("排序结果:", sorted_arr)

输出：

  
输入数组: [170, 45, 75, 90, 802, 24, 2, 66]  
排序结果: [2, 24, 45, 66, 75, 90, 170, 802]  

复杂度分析

• 时间复杂度：$O(nk)$（$k$为最大位数）。
• 空间复杂度：$O(n+k)$（辅助计数数组和输出数组）。
• 稳定性：稳定（依赖底层计数排序的稳定性）。

实际应用

1. 卡片排序机：早期机械式排序设备采用类似原理。 2. 大数据处理：如Hadoop中对海量整数排序。 3. 字符串字典序排序：如电话号码或车牌号排序。

优缺点

优点	缺点
线性时间复杂度优于比较排序（如快速排序）	仅适用于整数或固定格式字符串	稳定排序，保持相同键值的顺序	空间复杂度较高

扩展思考

• 如何优化基数排序对负数的处理？
• 比较基数排序与桶排序的异同。