您所在的位置:主页 > JAVA技术 >

理解计数排序算法的原理和实现

时间:2019-02-14 15:02来源:未知 作者:os 点击:

       计数排序(Counting sort)是一种稳定的线性时间排序算法,其平均时间复杂度和空间复杂度为O(n+k),其中n为数组元素的个数,k为待排序数组里面的最大值。同样具有线性时间排序的算法还有桶排序和基数排序,这一点不要搞混。 
       计数排序不是基于比较的排序,所以它的排序效率是线性的,在特定的场景下(已知数组的最大最小值,切数组元素整体量不是很大的情况下)排序效率极高,而基于比较排序的算法,其时间复杂度基本逃脱不了O(nlogn)的魔咒,当然能达到O(nlogn)的时间复杂度,已经是非常牛逼了,这里面典型的代表就是快速排序算法,因为没有其他条件限制,所以基本上是一种通用排序算法。 
       计数排序的算法的原理,其实是非常简单的,它不需要去跟其他元素比来比去,而是一开始就知道自己的位置,所以直接归位,在计数的该元素出现的词频数组里面,出现一次,就直接+1一次即可,如果没有出现改位置就是0,最后该位置的词频,就是代表其在原始数组里面出现的次数,由于词频数组的index是从0开始,所以最后直接遍历输出这个数组里面的每一个大于0的元素值即可。 
       我们先来看看简单版本的Java语言写的计数排序是如何实现的,假设有四个元素{2,1,0,1}。 
Java代码 
 
从上面可以看到,代码比较简单,但是并不是最优的,有三个缺点: 
       第一、不支持负数排序
       第二、第二在特定情况下使用空间较多,比如90-100仅仅有10个元素,但是数组却需要声明空间为100
       第三、第三排序不具有稳定性,重复元素的相对位置可能会变。 
       经过优化后的计数排序算法,需要遍历一次得到元素的最小值和最大值,然后构造空间范围可以优化为,max-min+1,而不是前面简单的max,此外在实现的时候,对于原数组统计词频的时候,使用的每个元素减去min之后的值,这样能保证结果落在词频数组的范围之内,最后,为了保证排序算法的稳定性,我们需要对词频进行一次sum操作,从1开始,把每个位置的词频设置为当前的元素的词频+前一个元素的词频,这个值就代表了其在原数组里面应该出现的位置,接着我们倒序遍历原始数组,这样就能保证稳定性。
优化后的代码如下: 
Java代码  
 
 
其中关键的地方有两个: 
       第一,在于理解计算max和min之后,需要使用原数组每一个元素减去min的转换值统计词频,特定情况下能节省存储空间,这样做的另一个好处是可以兼容负数的情况,因为每一个元素减去最小值之后,结果必定是大于等于0 
       第二,在于理解为什么采用词频求和的方式+倒序遍历原始数组的方式,能保证排序算法的稳定性 
理解了上面的两点,再来看优化后的计数排序就非常简单了。
总结: 
经典的计数排序分四个阶段: 
1,找出数组里面的最大值和最小值 
2,求出每个元素出现的词频(count) 
3,遍历词频数组求和 
4,反向遍历原始数组,进行目标数组填充,填充后的数组再遍历就是有序的。 
如果不考虑算法的稳定性和负数情况及特定情况的浪费空间,那么只需要前面的2步就可以了,如果想要保证稳定性,那么需要经过这4步计算。
计数排序在特定的情况下,排序效率极高,但是如果排序的计数空间范围过大,而实际元素个数非常小的情况,效率就会非常差,比如,我只有3个元素,3,1,500000,这样的情况其实是不适合用计数排序的,这一点需要注意。