首页 > 代码库 > 桶排序之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实现源码