计数排序算法，就是通过统计序列中各个元素出现的次数，完成对整个序列的升序或降序排序的算法，其时间复杂度为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