算法导论程序16--基数排序（Python）

夜空霓虹

于 2017-05-24 16:12:19 发布

阅读量958

点赞数

分类专栏：算法

本文链接：https://blog.csdn.net/zhang_xiaomeng/article/details/72677319

版权

算法专栏收录该内容

41 篇文章

订阅专栏

本文介绍了基数排序的基本概念，详细解析了基数排序的实现过程，包括确定整数位数、设置桶数组等关键步骤，并通过具体示例展示了排序效果。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

基数排序：

首先按照最低有效位进行排序，最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

import math
 
def sort(a, radix=10):
    """a为整数列表， radix为基数"""
    K = int(math.ceil(math.log(max(a), radix))) # 用K位数可表示任意整数
    print(K)
    bucket = [[] for i in range(radix)] # 不能用 [[]]*radix
    print(bucket)
    for i in range(1, K+1): # K次循环
        for val in a:
            bucket[int(val%(radix**i)/(radix**(i-1)))].append(val) # 析取整数第K位数字 （从低到高）
        
        del a[:]
        for each in bucket:
            a.extend(each) # 桶合并
        bucket = [[] for i in range(radix)]

运行结果：

>>> a=[329,457,657,839,436,720,355]
>>> sort(a)

>>> a
[329, 355, 436, 457, 657, 720, 839]