计数排序（Counting Sort）计数排序（Counting sort）是一种稳定的线性时间排序算法。 1. 基本思想 计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），然后进行分配、收集处理：
2. 实现逻辑
3. 动图演示
计数排序演示 举个例子，假设有无序数列nums=[2, 1, 3, 1, 5], 首先扫描一遍获取最小值和最大值，maxValue=5, minValue=1，于是开一个长度为5的计数器数组counter
4. 复杂度分析
当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n k)。。在实际工作中，当k=O(n)时，我们一般会采用计数排序，这时的运行时间为O(n)。 计数排序需要两个额外的数组用来对元素进行计数和保存排序的输出结果，所以空间复杂度为O(k n)。 计数排序的一个重要性质是它是稳定的：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序是相同的。也就是说，对两个相同的数来说，在输入数组中先出现的数，在输出数组中也位于前面。 计数排序的稳定性很重要的一个原因是：计数排序经常会被用于基数排序算法的一个子过程。我们将在后面文章中介绍，为了使基数排序能够正确运行，计数排序必须是稳定的。 5. 代码实现 C版本： 计数排序（C） Java版本： 计数排序（Java） 6. 优化改进 6.1场景分析： 举个极端的例子：如果排序的数组有200W个元素，但是这200W个数的值都在1000000-1000100，也就说有100个数，总共重复了200W次，现在要排序，怎么办？ 这种情况排序，计数排序应该是首选。但是这时候n的值为200W，如果按原来的算法，k的值10001000，但是此时c中真正用到的地方只有100个，这样对空间造成了极大的浪费。 6.2改进思路： 针对c数组的大小，优化计数排序 6.3改进代码： 计数排序改进（Java） 总结计数算法只能使用在已知序列中的元素在0-k之间，且要求排序的复杂度在线性效率上。 计数排序和基数排序很类似，都是非比较型排序算法。但是，它们的核心思想是不同的，基数排序主要是按照进制位对整数进行依次排序，而计数排序主要侧重于对有限范围内对象的统计。基数排序可以采用计数排序来实现。 源码地址：https://github.com/7-sevens/algorithm |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
