【排序算法】计数排序（CountSort）

作者：你好赵伟 | 2024-06-11 13:55:29

踩

一、定义

计数排序（CountSort）是一种非比较的排序，它的优势在于在对一定范围内的整数排序时，它的时间夫扎渡为为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。这是一种通过空间换取时间的算法，但是当O(k)＞O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，、堆排序、快速排序）✨

二、思路：

1、确定范围，找出待排序数组✨ a[] 的最大值(max)和最小值(最小值)

2、申请一个计数的数组记为 ✨count[]，并初始化为0，数组的大小由max-min+1决定（因为可以保证待排序所有的数都能记录上）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/703466