代码如下:
# -*- coding: utf-8 -*-
def insertion_sort(a): “””插入排序，作为桶排序的子排序””” n = len(a) if n 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))