基数排序：
首先按照最低有效位进行排序，最低位优先(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)]
运行结果： 【算法导论程序16--基数排序（Python）】
>>> a=[329,457,657,839,436,720,355]
>>> sort(a)>>> a
[329, 355, 436, 457, 657, 720, 839]
推荐阅读
- 集合的全排列（Java实现）
- 算法导论学习笔记——2.3.1分治法——习题2-4逆序对数
- 拓展欧几里得算法详解
- 算法导论程序15-计数排序（Python）
- 算法导论 — 8.3 基数排序
- 算法导论 基数排序
- RSA模重复平方算法小示例
- 【算法导论之四】计数排序
- 算法导论计数排序实现