思路
先比较个位数,得到一个新的序列;再按照十位数排序,在上一个新序列的基础上又得到
一个新的序列;然后再按照百位数排序,在上一个新序列的基础上又得到一新的序列;
只到排到所有数中的最高位,依次输出列表,排序结束。
栗子
例:li=[12,90,4,894,66]
可以看到,最高位有百位,因此我们可以将li看成是[012,090,004,894,066]
######################################################################################
[012,090,004,894,066]按照个位排序:
894
090 012 004 066
0 1 2 3 4 5 6 7 8 9 --->li=[090,012,004,894,066]
######################################################################################
######################################################################################
[090,012,004,894,066]按照十位排序:
894
004 012 066 090
0 1 2 3 4 5 6 7 8 9 --->li=[004,012,066,090,894]
######################################################################################
######################################################################################
li=[004,012,066,090,894]按照百位排序:
090
066
012
004 894
0 1 2 3 4 5 6 7 8 9 --->li=[004,012,066,090,894]
######################################################################################
排序完成,得到li=[004,012,066,090,894]
源码
# 基数排序
@clocked
def radix_sort(li):
n = 1
while True:
buckets = [[] for _ in range(10)]
flag = 0
for i in range(len(li)):
digit = li[i] // n % 10 # 依次取出个位,十位,百位的数字...
buckets[digit].append(li[i])
if digit != 0: flag = 1 # 只要有所有的数中,有一个数它的最高位不为0,说明循环就没有结束
n *= 10
li.clear()
for bucket in buckets: li.extend(bucket)
print(li)
if flag == 0:
break
测试
同步更新于个人博客系统:python实现基数排序