tmp = []
def bucket_sort(old):
for i in range(len(old)):
tmp.append([]) for i in old:
tmp[int( i * len(old) )].append(i) for i in range(len(old)):
#tmp[i].sort()
insert_sort(tmp[i]) for i in range(len(old)):
if(len(tmp[i]) > 0):
print tmp[i] #test case
old = [0.3333333333333333, 0.8333333333333334, 0.5, 0.0, 0.3333333333333333, 0.5, 0.0, 0.5]
bucket_sort(old)
insert_sort(old)
print old
桶排序假设输入是在[0,1)之间的随机均匀分布。
桶排序的时间复杂度O(N)
A[n]: 原始数组
B[n]: B[i] = A[i] * n
C[n]: C[i]中存入链表的头指针
step 1
B[i] = A[i] * n
step 2
根据B[i] 的整数部分,将A[n]进行划分,划分后的A[i]存入对应的C[i]的链表中
step 3
对C[i]中的链表分别排序
step 4
将排序后的C[i],从0至n-1进行合并