摘要：
34bucks=dict（）#Bucket 5foriinA:[]）#默认情况下，每个Bucket都是空列表。7桶[i]。append（i）#将元素89A添加到对应的bucket_Sort=[]10foriinrange（min（A），max（A）+1）：#排序简单整数序列A=[2,5]A=bucksort（A）printa>；分数）：
桶排序的时间复杂度是O(M+N)，通过建立对原始数据的有序统计表，实现非常快速的排序过程
可以用hashtable（或者dict）实现，查询复杂度为O(1)
贴代码：
1 # 简单桶排序 从小到大 2 def bucksort(A): 3 4 bucks = dict() # 桶 5 for i in A: 6 bucks.setdefault(i,[]) # 每个桶默认为空列表 7 bucks[i].append(i) # 往对应的桶中添加元素 8 9 A_sort = [] 10 for i in range(min(A), max(A)+1): 11 if i in bucks: # 检查是否存在对应数字的桶 12 A_sort.extend(bucks[i]) # 合并桶中数据 13 14 return A_sort
下面是运行结果：
# 对单纯整数数列进行排序 A = [2,3,5,4,6,7,3,3,0,8,5] a = bucksort(A) print a >>> [0, 2, 3, 3, 3, 4, 5, 5, 6, 7, 8]
《啊哈》中还提到了对非数字类型排序时，桶排序的应用，其思路也可以用python这样实现：
假设我们要对学生进行按分数排序：
1 # 包含其他元素的桶排序 2 # element：人名，分数 3 class Person: 4 def __init__(self,name,score): 5 self.name = name 6 self.score = score 7 def __repr__(self): # 覆写打印输出 print Person() 8 return self.name + "-" + str(self.score) 9 10 11 def bucksort2(A): 12 bucks = dict() 13 for a in A: 14 bucks.setdefault(a.score,[]) # 以个人分数为评价排列标准 15 bucks[a.score].append(a) # 在相同分数的桶中添加人 16 17 A_sort = [] 18 scorelist = [a.score for a in A] # 将人员列表中所有人的分数取出 19 for i in range(min(scorelist), max(scorelist)+1): 20 if i in bucks: 21 A_sort.extend(bucks[i]) 22 23 return A_sort
输出结果：
# 对人进行排序 B = [Person('huhu',5),Person('haha',3),Person('xixi',5),Person('hengheng',2),Person('gaoshou',8)] b = bucksort2(B) print b >>> [hengheng-2, haha-3, huhu-5, xixi-5, gaoshou-8]