首页 > 代码库 > 桶排序之python实现源码
桶排序之python实现源码
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 caseold = [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进行合并
桶排序之python实现源码
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。