1 #-*- coding: UTF-8 -*-
2 import numpy as np
3
4 def RadixSort(a):
5 i = 0 #初始为个位排序
6 n = 1 #最小的位数置为1(包含0)
7 max = np.max(a) #得到带排序数组中最大数
8 while max/(10**n) > 0: #得到最大数是几位数
9 n += 1
10 while i < n:
11 bucket = {} #用字典构建桶
12 for x in xrange(0,10):
13 bucket.setdefault(x, []) #将每个桶置空
14 for x in a: #对每一位进行排序
15 radix =(x / (10**i)) % 10 #得到每位的基数
16 bucket[radix].append(x) #将对应的数组元素加入到相应位基数的桶中
17 j = 0
18 for k in xrange(0, 10):
19 if len(bucket[k]) != 0: #若桶不为空
20 for y in bucket[k]: #将该桶中每个元素
21 a[j] = y #放回到数组中
22 j += 1
23 i += 1
24
25 if __name__ == '__main__':
26 a = np.random.randint(0, 1000, size = 10)
27 print "Before sorting..."
28 print "---------------------------------------------------------------"
29 print a
30 print "---------------------------------------------------------------"
31 RadixSort(a)
32 print "After sorting..."
33 print "---------------------------------------------------------------"
34 print a
35 print "---------------------------------------------------------------"