# python每日算法 | 揭开计数排序的秘密

> 来源：梦飞idc云平台 | 原文：https://www.mfisp.com/12826.html | 发布：2022-11-18 | 更新：2022-11-18 | 分类：建站教程、投稿分享

## 计数排序

 

## 什么是计数排序

 
 
- ![python每日算法 | 揭开计数排序的秘密](https://www.mfisp.com/wp-content/uploads/2021/10/20221118001800AiUErq.gif) 

   

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

 

简单来说计数排序就是对对列表进行排序，已知列表中的范围数都在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)

---
本页由 梦飞idc云平台（https://www.mfisp.com）提供。站点导航见 https://www.mfisp.com/llms.txt