目录Python全系列 教程
3567个小节阅读：5931.1k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
计数排序不是基于比较的排序算法，通过统计元素数量来实现排序。
根据待排序集合中最大元素和最小元素的差值范围，申请额外空间；
遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内；
对额外空间内数据进行计算，得出每一个元素的正确位置；
将待排序集合每一个元素移动到计算得出的正确位置上。
xxxxxxxxxxdef count_sort(arr): # 如果数组长度小于 2 则直接返回 if len(arr) < 2: return arr # 获取数组中最小值 min_num = min(arr) # 获取数组中最大值 max_num = max(arr) count = max_num - min_num # 开辟一个计数列表(长度为取值范围) count_list = [0 for _ in range(count+1)] # 循环操作下标位置数+1(等于是记录每个数在数组中出现了多少次) for val in arr: index = val-min_num count_list[index] += 1 # 原数组清空，留待下面重新插入 arr.clear() # 遍历计数列表中的值和下标(值的数量)， # 从0开始，所以最终是从小到大排序 for ind, val in enumerate(count_list): # 下面按照值中的数量进行循环 for i in range(val): # 有多少，则会追加多少次 arr.append(ind+min_num) return arr
if __name__ == "__main__": print('----------- 排序前数组内容 -----------------') arr = [2, 3, 8, 7, 1, 2, 3, 2, 7, 3, 9, 8, 2, 1, 6, 2, 4, 6, 9, 2] print(arr) count_sort(arr) print('------------ 排序后的结果 ------------------') print(arr)时间复杂度 $ O(n+m) $：涉及遍历 nums 和遍历 counter ，都使用线性时间。一般情况下 n≫m ，时间复杂度趋于 $ O(n) $。
空间复杂度 $ O(n+m) $、非原地排序：借助了长度分别为 $n$ 和 $m$ 的数组 res 和 counter 。
稳定排序：由于向 res 中填充元素的顺序是“从右向左”的，因此倒序遍历 nums 可以避免改变相等元素之间的相对位置，从而实现稳定排序。实际上，正序遍历 nums 也可以得到正确的排序结果，但结果是非稳定的。
提示
计数排序只适用于非负整数
若想将其用于其他类型的数据，需要确保这些数据可以转换为非负整数，并且在转换过程中不能改变各个元素之间的相对大小关系。例如，对于包含负数的整数数组，可以先给所有数字加上一个常数，将全部数字转化为正数，排序完成后再转换回去。
实时效果反馈
1. 关于计数排序算法，说法正确的是？
A 计数排序会分配新数组来存储每个元素出现的次数
B 计数排序记录次数的数组长度为元素总个数
C 计数排序排序时，需要比较元素之间的大小
D 计数排序需要将数列分成若干个子序列
答案
1=>A