python 基数 计数 排序

#!/usr/bin/python
# 基数排序
# 将列表中的数按照基数进行排序 先排序个位的数 在排序十位的 依次类推可以
def radix_sort(li):
    max_mun = max(li) #确定列表中最大的值
    it = 0
    while 10 ** it <= max_mun: #按照最大的数的位数进行循环 10 ** it 当it = 1时 10 ** it 表示次方 10的1次方
        buckets = [[] for _ in range(10)] #生成10个桶（列表）
        for var in li:
            digit = (var // 10 ** it) % 10 # 将列表中的数进行分桶 进行数的除法和取余可以获得数值的个位数
            buckets[digit].append(var)
        
        li.clear() #清空列表 
        
        for buc in buckets: 
            li.extend(buc) # 将数放回到原来列表
               
        it += 1


————————————————————
#!/usr/bin/python
# 计数排序
# 对列表进行排序，已知列表中的值的数都在0-100之间
def count_sort(li,max = 100):
    count_list = [0 for _ in range(max+1)] #生成一个0到100的长度的列表 用来存放原来列表的值
    for val in range(li): #循环原来列表，将新列表中的相同的数值进行加1 
        count_list[val] += 1

    li.clear() # 清空原来列表 不使用新的内存 节省空间

    for ind,val in enumerate(count_list): # 循环新的列表。取出值和下标
        for i in range(val): #循环每个数出现的次数
            li.append(ind) # 将出现的数放进列表 

#时间复杂度为 O(n) 但是存在使用条件 ， 和列表中的数值范围相关

python 基数 计数 排序

原文：https://www.cnblogs.com/ikai/p/11636366.html