介绍计数排序不是基于比较的排序算法。它的核心是将输入的数据值转换成一个key，存储在一个额外的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入数据必须是一定范围内的整数。它的基本思想是：给定输入序列中的每个元素x，确定序列中值小于或等于x的元素个数，然后将x直接存储在最终排序序列的正确位置。算法实现步骤根据待排序集合中最大元素和最小元素的差值范围申请附加空间；遍历待排序集合，记录元素值对应的额外空间中每个元素出现的次数；在多余的空间进行数据处理计算得到每个元素的正确位置；将要排序的集合中的每个元素移动到计算出的正确位置。Python代码实现#counting_sort代码实现fromtypingimportListdefcounting_sort(arr:List[int]):max=min=0foriinarr:ifimax:max=icount=[0]*(max-min+1)forjinrange(max-min+1):count[j]=0forindexinarr:count[index-min]+=1index=0forainrange(max-min+1):forcinrange(count[a]):arr[index]=a+minindex+=1#testdataif__name__=='__main__':importrandomrandom.seed(54)arr=[random.randint(0,100)for_inrange(10)]print("原始数据：",arr)counting_sort(arr)print("计数排序结果",arr)#输出原始数据：[17,56,71,38,61,62,48,28,57,42]统计排序结果[17,28,38,42,48,56,57,61,62,71]动画演示算法分析时间复杂度数据获取取值范围为常数k，待排序元素个数为n，总时间复杂度为$O(n+k)$。空间复杂度计数排序只需要$O(k)$的额外空间复杂度，因此计数排序的空间复杂度为$O(k)$。稳定性计数排序不会改变相等元素的相对位置，因此计数排序是稳定的。综合评价时间复杂度（平均）时间复杂度（最好）时间复杂度（最差）空间复杂度排序稳定性$O(n+k)$$O(n+k)$$O(n+k)$$O(k)$out-placeStable联系我们个人博客网址：http://www.bling2.cn/Github地址：https://github.com/lb971216008/Use-Python-to-Achieve关于专栏：https://zhuanlan.zhihu.com/Use-Python-to-Achieve小专栏：https://xiaozhuanlan.com/Use-Python-to-Achieve博客园：https://www.cnblogs.com/Use-Python-to-Achieve
