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