python算法学习之计数排序实例

复制代码 代码如下:

-- coding: utf-8 --

def _counting_sort(A, B, k):
"""计数排序，伪码如下：
COUNTING-SORT(A, B, k)
1 for i <- 0 to k // 初始化存储区的值
2 do C[i] <- 0
3 for j <- 1 to length[A] // 为各值计数
4 do C[A[j]] <- C[A[j]] + 1
5 ▷ C[i]包含等于i的元素个数
6 for i <- 1 to k // 求计数和，确定<=各值的元素数
7 do C[i] <- C[i] + C[i-1]
8 ▷ C[i]包含小于或等于i的元素个数
9 for j <- length[A] downto 1
10 do B[C[A[j]]] <- A[j] // 将A[j]值放到对应位置
11 C[A[j]] <- C[A[j]] - 1 // 避免元素相同时覆盖同一位置

T(n) = θ(n)

Args:  
    A (Sequence): 原数组  
    B (Sequence): 结果数组  
    k (int): 值上限，假定了所有元素介于[0,k]  
"""  
len_c = k + 1  
C = [0] * len_c  
for a in A:  
    C[a] = C[a] + 1  
for i in range(1, len_c):  
    C[i] = C[i] + C[i-1]  
for a in A[::-1]:  
    B[C[a]-1] = a  
    C[a] = C[a] - 1

def counting_sort(A):
"""假定A数组所有元素都介于[0,len(A)-1]"""
B = [0] * len(A)
_counting_sort(A, B, len(A) - 1)
return B

if name == 'main':
import random, timeit

items = range(10000)  
random.shuffle(items)

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

def test_counting_sort():  
    print(items)  
    sorted_items = counting_sort(items)  
    print(sorted_items)

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