document.write('基数排序(radix sort)属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort或bin sort)，排序的过程就是将最低位优先法用于单关键字的情况。下面以[73，22，93，43，55，14，28，65，39，81]为例来介绍排序的基本思想。
(1)根据个位数把这些数字分配到编号为0～9的桶子中，如下所示：
桶编号 桶中的数
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
(2)接下来将这些桶子中的数值重新串接起来，成为以下的数列： 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再十位数来分配：
桶编号 桶中的数
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
(3)接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
此时数组的排序已经完成了；如果排序的对象有三位数以上，那么持续进行以上的动作直至最高位数为止。示例代码如下：
import math
def radix_sort(lists,radix=10):
k=int(math.ceil(math.log(max(lists),radix)))
bucket=[[] for i in range(radix)]
for i in range(1,k+1):
for j in lists:
bucket[j/(radix**(i-1))%(radix**i)].append(j)
del lists[:]
for z in bucket:
lists+=z
del z[:]
return lists
if __name__=="__main__":
lists=[3,4,2,8,9,5,1]
print \'排序前序列为:\',
for i in lists:
print i,
print \'\\n排序后结果为:\',
for i in (radix_sort(lists)):
print i,
程序的运行结果为：
排序前序列为：3 4 2 8 9 5 1
排序后结果为：1 2 3 4 5 8 9
LSD的基数排序适用于位数小的数列，如果位数多的话，那么使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数。
在某些时候，基数排序法的效率高于其他的稳定性排序法。
');