复制代码 代码如下:

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