热搜： Python PHP vue dedecms 编程

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

发布时间：2024-04-27 16:57:45 来源：好代码

.

小村上空升起袅袅炊烟，好像一个身穿白纱的少女在翩翩起舞，在夕阳的照耀下婀娜多姿。

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