计算规则
假设需要排序的列表是[1,0,3,5,3,2,2]，从最小值0到最大值5，使用一个列表存储0~5之间所有数的出现次数
计数结果：[1,1,2,2,0,1]即0出现1次，1出现1次，2出现2次，3出现2次，4出现0次，5出现1次
必须要计算0~5之间的所有数出现的次数，4在原始列表中没有出现也要记录次数
计数排序的局限性
因为必须要统计最小值到最大值之间所有数出现的次数。假设原始列表是[1,0,5000]，就需要统计0~5000之间所有数的出现次数（统计次数的列表长度为5001），这样很浪费内存。
所以只适用于数值跨度比较小的情况
代码实现
def count_sort(li,max_num):
tmp_list = [0 for _ in range(max_num+1)] #[0,0,0,0...]表示0,1,2,3,4...出现的次数，初始是0次
for i in li:
tmp_list[i] += 1
res_list = []
for index, item in enumerate(tmp_list):#index这个数出现了item次
for _ in range(item):
res_list.append(index)
return res_list
li = [0,3,2,1,4,2,1,3,3,0]
res_list = count_sort(li,4)
print(res_list)
>>>[0, 0, 1, 1, 2, 2, 3, 3, 3, 4]
时间复杂度
这里只考虑适用计数排序情况下的时间复杂度，假设原始列表最小值和最大值之间的数值都出现过
def count_sort(li,max_num):
tmp_list = [0 for _ in range(max_num+1)]#适用情况下，小于O(n)
for i in li:#O(n)
tmp_list[i] += 1
res_list = []
for index, item in enumerate(tmp_list):#这里的两层循环最后res_list.append()的次数和li长度相同，所以也是O(n)
for _ in range(item):
res_list.append(index)
return res_list
适用情况下，时间复杂度是O(n)
