算法|算法导论笔记——水桶排序（基数排序）算法|python

这次是计数排序的升级版，若是计数排序还没有搞懂，先去看看我的前一篇。
计数排序是用空间换时间的算法，若k太大，它的效率会下降很快，而且会消耗很多内存，所以通常是在重复的元素很多，且跳跃不太大的情况下使用。废话不多先上代码：

import math def bucketsort(A,maxValue): #采用二进制分组，比10进制分组更精确 #step1 得到maxValue的二进制位数 nstr = bin(maxValue) count = len(nstr)-2 #step2 取得最佳桶容量r,当r = lgn时效率最快 r = int(math.log(count,2)) #获得分组二进制位数 boost = count/r #step3 得到掩码 b2 = boost andn = 0 while b2: b2-=1 andn += 1<>pullcount #使用掩码屏蔽多余的位数 a &= andn C[a]+=1 B.append(0) for i in range(1,k): C[i]+=C[i-1] for jk in reversed(A): #和上面同理 j = jk>>pullcount j &= andn B[C[j]-1] = jk C[j]-=1 A = B return A

【算法|算法导论笔记——水桶排序（基数排序）】效率O((bn)/(lgn))
网上找了很多桶子排序代码，发现很多效率都不尽人意，不但慢于快速排序，甚至与普通插入排序都差不多了。
参考麻省理工算法导论公开课，使用二进制分桶，使用计数排序实现底层排序，大大加快了效率。