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