计数排序

什么是计数排序

• 

 

 

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

简单来说计数排序就是对对列表进行排序，已知列表中的范围数都在0~100之间。设计时间复杂度为O(n)的算法。

实例讲解

现有列表：

1 3 2 4 1 2 3 1 3 5

首先建一个列表（元素为下标），接下来遍历计数每个元素有多少个，创建一个新列表存储数量。

0    0

1    0

2    0

3    0

4    0

5    0

第一次：

0    0

1    1

2    0

3    0

4    0

5    0

第二次

0    0

1    1

2    0

3    1

4    0

5    0

……

最后

0    0

1    3

2    2

3    3

4    1

5    1

接下来得到最终列表：

1 1 1 2 2 3 3 3 4 5

（列表写的简化，见谅）

代码的实现

def count_sort(lst,max_count=100):  # 传入列表和最大值
 
    count = [0 for i in range(max_count+1)]  # 计数列表
 
    for val in lst:
 
        count[val] += 1  # val即为下标
 
    lst.clear()  # 写到lst中之前需要情况lst
 
    for ind,val in enumerate(count):  # 下标和值
 
        for i in range(val):  # 查看个数并增加到列表中
 
            lst.append(ind)
 
 
 
import random
 
lst1 = [random.randint(0,5) for i in range(10)]
 
print(lst1)
 
count_sort(lst1)
 
print(lst1)
 
# 输出结果
 
# [2, 2, 0, 1, 4, 3, 5, 4, 0, 3]
 
# [0, 0, 1, 2, 2, 3, 3, 4, 4, 5]

 

计数排序的时间复杂度

第一层循环count“+”了n次，第二层是append“+”n次，两层循环循环加起来是2n，因此时间复杂度为O(n)