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