Python实现基数排序算法详解与代码示例

基数排序的核心原理

基数排序（Radix Sort）不依赖元素间的直接比较，而是根据整数的每一位数值进行分组。它通常采用最低位优先（LSD）策略，从个位开始，依次向高位推进。每一轮都会将当前列表中的数字按对应位上的值放入 0～9 共十个桶中，随后按桶的顺序重新拼接。由于该过程在分配和收集时保持原有相对顺序，因此它是一种稳定排序算法。

该算法的时间复杂度为 O(k × n)，其中 n 为数据量，k 为最大整数的位数。当 k 相对较小且数据分布集中时，排序效率显著优于基于比较的 O(n log n) 算法。

环境与准备条件

实现基数排序无需安装第三方库，仅依赖 Python 标准内置函数。建议在 Python 3.x 环境下运行，以兼容现代解释器特性。原始代码中使用的旧版语法需适配，主要涉及 xrange 移除与 print 语句的函数化调整。

代码实现步骤

第1步：初始化输入数据与位宽参数

目的：构建待排序的整数序列，并明确需要处理的最高位数阈值。

import random

def radix_sort_prepare(nums):
    # 自动计算实际最大位数，避免硬编码导致高位空缺或截断
    max_val = max(nums) if nums else 0
    max_digits = len(str(max_val)) if nums else 0
    return nums, max_digits

第2步：按数位提取键值并执行桶分配

目的：通过数学取余运算定位当前处理位，将元素打入对应的临时容器。

# 定义十个空桶用于存放当前位的数字
buckets = [[] for _ in range(10)]
for num in nums:
    # 公式解析：先右移丢弃低位，再取模获取当前位数值
    digit_index = (num // 10 ** current_digit) % 10
    buckets[digit_index].append(num)

第3步：按序收集桶内元素并覆盖原数组

目的：打乱后的桶内数据按桶索引从小到大展开，恢复为线性列表。

nums = [num for bucket in buckets for num in bucket]

第4步：循环迭代至最高位完成全局有序

目的：重复步骤二与三，直至个、十、百……所有位均被遍历排序。

for digit in range(max_digits):
    buckets = [[] for _ in range(10)]
    for num in nums:
        digit_index = (num // 10 ** digit) % 10
        buckets[digit_index].append(num)
    nums = [num for bucket in buckets for num in bucket]
return nums

完整可运行示例

import random

def radix_sort(nums):
    if not nums:
        return nums
    max_digits = len(str(max(nums)))
    for digit in range(max_digits):
        buckets = [[] for _ in range(10)]
        for num in nums:
            buckets[(num // 10 ** digit) % 10].append(num)
        nums = [num for bucket in buckets for num in bucket]
    return nums

if __name__ == "__main__":
    # 生成大规模随机整数样本
    sample_data = [random.randint(1, 10**8) for _ in range(10000)]
    sorted_data = radix_sort(sample_data)
    print("排序前样本数:", len(sample_data))
    print("排序后前十项:", sorted_data[:10])
    print("排序后末十项:", sorted_data[-10:])

运行验证与排错指南

• 版本兼容性提示：原文使用的 xrange 仅在 Python 2 中存在，Python 3 已将其合并至 range 中，直接使用会引发 NameError。同时 print i 需改为函数调用形式 print(i)。
• 负数支持限制：基础基数排序逻辑针对正整数设计。若输入包含负数，建议先分离正负两组分别排序，或使用偏移量统一转为正整数处理。
• 内存占用观察：每次迭代都会创建新的桶列表，数据量极大时可考虑复用容器结构以降低 GC 压力。

简要总结

基数排序通过位分解与桶映射避开了传统比较开销，特别适合位数有限的大批量整数场景。掌握其 // 10**k % 10 的取位公式与多轮收集机制，即可在 Python 中高效落地。以上就是 Python 实现基数排序算法的详细内容，更多关于常用排序算法优化的资料请关注本站其它相关文章！