计数排序算法,就是通过统计序列中各个元素出现的次数,完成对整个序列的升序或降序排序的算法,其时间复杂度为O(n)。该算法时间复杂度很低,甚至比之前介绍过的 快速排序算法 还要低,但该算法的条件比较苛刻,一是要求待排序元素都是整数,二是数值不能太大(通常为100以下)。

实现思路

1)遍历序列,统计元素出现次数;

2)遍历统计序列,按次数展开序列。

代码示例

def count_sort(arr, max_count=100):
    # 统计出现次数
    count_list = [0 for _ in range(max_count+1)]
    for i in arr:
        count_list[i] += 1
    # 展开统计序列
    arr.clear()
    for k,v in enumerate(count_list):
        arr.extend([k] * v)

lst = [27, 13, 35, 10, 3, 33]
count_sort(lst, 100)
print(lst)

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/260