基本思想
原理和桶排序有些类似，不过基数排序每次按照不同的规则多次使用桶，然后达到排序的目的。
示例
[19,30,28,51,44,62,7,68,85,17]
- 首先将序列根据个位数的值装入标号为0到9的十个桶中
0 30
1 51
2 62
3
4 44
5 85
6
7 7 17
8 28 68
9 19 - 依次取出这些序列，组成新的序列[30,51,62,44,85,7,17,28,68,19]，然后根据十位数的值依次的装入桶中。如果没有十位数，则是0.
0 7
1 17 19
2 28
3 30
4 44
5 51
6 62 68
7
8 85
9 - 取出这些值，组成新的序列[7,17,19,28,30,44,51,62,68,85],则这个新的序列就是排序完成的。
python代码实现
#!/usr/bin/python
# encoding: utf-8
import random
# 基数排序
def radixSort(alist):
# 列表中最大值的位数
m = max(alist)
d = 0
while m > 0:
d += 1
m = m // 10
# d轮装桶
for k in xrange(d):
# 构造10个桶
bucket = [[] for i in xrange(10)]
# 装桶
for i in alist:
bucket[i/(10**k)%10].append(i)
# 取出桶中的值，更新序列
alist = [j for i in bucket for j in i]
return alist
if __name__ == '__main__':
# 随机生成10000个1到999的数
alist = [random.randint(1, 999) for i in xrange(10000)]
alistNew = radixSort(alist)
print alistNew
