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))
上一篇: PHP用函数嵌入网站访问量计数器
下一篇: 美图秀秀如何把普通照片变成复古色效果?