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