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

# -*- 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))