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

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