Python实现基数排序（从零开始掌握非比较排序算法）

为什么选择基数排序？

• 时间复杂度为 O(d × (n + k))，其中 d 是最大数的位数，n 是元素个数，k 是基数（如10进制中k=10）
• 对于位数固定的整数，可视为线性时间排序
• 稳定排序：相等元素的相对顺序不会改变
• 非常适合用于处理大量整数数据

Python实现基数排序步骤详解

我们将按照以下步骤实现基数排序：

1. 找出数组中最大值，确定最大位数
2. 从个位开始，对每一位执行计数排序
3. 重复直到处理完所有位数

完整代码实现

def counting_sort_for_radix(arr, exp):    """    对数组arr按照exp位（1, 10, 100...）进行计数排序    """    n = len(arr)    output = [0] * n          # 输出数组    count = [0] * 10          # 计数数组（0-9）    # 统计当前位上每个数字出现的次数    for i in range(n):        index = arr[i] // exp        count[index % 10] += 1    # 将count[i]变为实际位置（累加）    for i in range(1, 10):        count[i] += count[i - 1]    # 从后往前构建输出数组（保证稳定性）    i = n - 1    while i >= 0:        index = arr[i] // exp        output[count[index % 10] - 1] = arr[i]        count[index % 10] -= 1        i -= 1    # 将排序结果复制回原数组    for i in range(n):        arr[i] = output[i]def radix_sort(arr):    """    基数排序主函数    """    # 找出最大值以确定最大位数    max_val = max(arr)    # 从个位开始，对每一位进行计数排序    exp = 1    while max_val // exp > 0:        counting_sort_for_radix(arr, exp)        exp *= 10    return arr# 测试示例if __name__ == "__main__":    test_array = [170, 45, 75, 90, 2, 802, 24, 66]    print("原始数组:", test_array)    sorted_array = radix_sort(test_array.copy())    print("排序后数组:", sorted_array)

代码解析

上面的代码包含两个核心函数：

• counting_sort_for_radix()：针对某一位（由exp参数指定，如1表示个位，10表示十位）执行计数排序
• radix_sort()：主函数，先找到最大值确定循环次数，然后逐位调用计数排序

运行上述代码，你会看到输出：

原始数组: [170, 45, 75, 90, 2, 802, 24, 66]排序后数组: [2, 24, 45, 66, 75, 90, 170, 802]

注意事项与适用场景

虽然Python基数排序效率高，但也有局限性：

• 仅适用于整数或可转换为整数的数据（如固定长度字符串）
• 需要额外空间存储中间结果
• 当数值范围极大时，可能不如比较排序高效

但在处理大量整数（如学号、ID、电话号码等）时，非比较排序算法如基数排序往往能带来显著性能提升。

总结

通过本教程，你已经掌握了基数排序算法的基本原理和Python排序教程中的具体实现。记住，理解算法背后的逻辑比死记代码更重要。尝试修改代码处理负数，或扩展为支持字符串排序，是巩固知识的好方法！

希望这篇关于Python基数排序的教程对你有帮助！动手实践是掌握算法的最佳途径。