计数排序 的思想十分简单，就是统计每个数字出现的次数。它是一种非基于比较的排序算法，其是通过额外的空间换取时间的方式，来实现更加高效的排序。😇😇😇
1、假设我们有一个长度为 n 的待排序序列，其所有元素组成的集合为 S，集合的数据范围为 0 - k。
我们只需要定义一个大小为 k 的数组 count[] 用来统计每个数字出现的次数；
2、之后按照统计数组 count[] 下标顺序将数字放入原数组中即可完成排序。
计数排序时间复杂度为 O(n + k)，其中 n 为数据元素个数， k 为数据元素范围大小。
当数据范围大小 k 恰好和 n 相等时，时间复杂度为 O(n)。
计数排序有几大局限性
1、当我们的数据范围非常大时，我们需要开辟很多的空间。夸张地讲，假如有1000万个数据，数据范围非常大，这个时候用计数排序是十分低效的；
2、当我们的数据之间跨度比较大，比如说出现了数字 1，但是下一个出现的数字是10000，2-9999中间的数字都没有出现，那么也浪费了很多的空间；
3、当我们的数据范围无法确定时，我们不知道要开辟多少大小的 count[] 数组；
4、计数排序还有一大局限性是，他不可以对小数进行排序，毕竟统计数组的下标都是整数呢。😏
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/15832.html