python算法学习之桶排序算法实例(分块排序)

发表于 5年以前 | 总阅读数：1092 次

复制代码 代码如下:

-- coding: utf-8 --

def insertion_sort(A):
"""插入排序，作为桶排序的子排序"""
n = len(A)
if n <= 1:
return A
B = [] # 结果列表
for a in A:
i = len(B)
while i > 0 and B[i-1] > a:
i = i - 1
B.insert(i, a);
return B

def bucket_sort(A):
"""桶排序，伪码如下：
BUCKET-SORT(A)
1 n <- length[A] // 桶数
2 for i <- 1 to n
3 do insert A[i] into list B[floor(nA[i])] // 将n个数分布到各个桶中
4 for i <- 0 to n-1
5 do sort list B[i] with insertion sort // 对各个桶中的数进行排序
6 concatenate the lists B[0],B[1],...,B[n-1] together in order // 依次串联各桶中的元素

桶排序假设输入由一个随机过程产生，该过程将元素均匀地分布在区间[0,1)上。  
"""  
n = len(A)  
buckets = [[] for _ in xrange(n)] # n个空桶  
for a in A:  
    buckets[int(n * a)].append(a)  
B = []  
for b in buckets:  
    B.extend(insertion_sort(b))  
return B

if name == 'main':
from random import random
from timeit import Timer

items = [random() for _ in xrange(10000)]

def test_sorted():  
    print(items)  
    sorted_items = sorted(items)  
    print(sorted_items)

def test_bucket_sort():  
    print(items)  
    sorted_items = bucket_sort(items)  
    print(sorted_items)

test_methods = [test_sorted, test_bucket_sort]  
for test in test_methods:  
    name = test.__name__ # test.func_name  
    t = Timer(name + '()', 'from __main__ import ' + name)  
    print(name + ' takes time : %f' % t.timeit(1))