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

计数排序(Counting sort)是一种稳定的线性时间排序算法,其平均时间复杂度和空间复杂度为O(n+k),其中n为数组元素的个数,k为待排序数组里面的最大值。同样具有线性时间排序的算法还有桶排序和基数排序,这一点不要搞混。

计数排序不是基于比较的排序,所以它的排序效率是线性的,在特定的场景下(已知数组的最大最小值,切数组元素整体量不是很大的情况下)排序效率极高,而基于比较排序的算法,其时间复杂度基本逃脱不了O(nlogn)的魔咒,当然能达到O(nlogn)的时间复杂度,已经是非常牛逼了,这里面典型的代表就是快速排序算法,因为没有其他条件限制,所以基本上是一种通用排序算法。

计数排序的算法的原理,其实是非常简单的,它不需要去跟其他元素比来比去,而是一开始就知道自己的位置,所以直接归位,在计数的该元素出现的词频数组里面,出现一次,就直接+1一次即可,如果没有出现改位置就是0,最后该位置的词频,就是代表其在原始数组里面出现的次数,由于词频数组的index是从0开始,所以最后直接遍历输出这个数组里面的每一个大于0的元素值即可。

我们先来看看简单版本的Java语言写的计数排序是如何实现的,假设有四个元素{2,1,0,1}。

public static void  simpleCountSort(){
        int nums[]={2,1,0,1};

        int maxNum=2;

        int storeArray[]=new int[maxNum+1];

        //词频计数
        for(int i=0;i<nums.length;i++){
            storeArray[nums[i]]++;
        }

        System.out.println("==============排序后==============");

        int ndx=0;
        //遍历计数后的词频数组
        for (int i = 0; i <storeArray.length ; i++) {
            //对于每个index的值进行循环,输出,因为有可能重复
            while (storeArray[i]>0){
                nums[ndx]=i;//把词频数组的值,放回原数组里面,
                ndx++;//替换一个数,就索引自增
                storeArray[i]--;//词频减1,防止死循环
            }
        }


        System.out.println(Arrays.toString(nums));



    }

从上面可以看到,代码比较简单,但是并不是最优的,有三个缺点:

第一不支持负数排序,第二在特定情况下使用空间较多,比如90-100仅仅有10个元素,但是数组却需要声明空间为100,第三排序不具有稳定性,重复元素的相对位置可能会变。

经过优化后的计数排序算法,需要遍历一次得到元素的最小值和最大值,然后构造空间范围可以优化为,max-min+1,而不是前面简单的max,此外在实现的时候,对于原数组统计词频的时候,使用的每个元素减去min之后的值,这样能保证结果落在词频数组的范围之内,最后,为了保证排序算法的稳定性,我们需要对词频进行一次sum操作,从1开始,把每个位置的词频设置为当前的元素的词频+前一个元素的词频,这个值就代表了其在原数组里面应该出现的位置,接着我们倒序遍历原始数组,这样就能保证稳定性。 具体的算法过程,我推荐一个youtube上的一个视频,演示的最常清晰:

https://m.youtube.com/watch?v=TTnvXY82dtM

优化后的代码如下:

public static int[] countSort(int []a){
        //使用最大值和最小值的方式是一种优化的计数排序
        //可以兼容负数的情况,同时能减少存储的空间,比如最大数是100,但实际上只有90-100这10个数字
        //所以仅仅需要10个存储空间即可
        int max = a[0], min = a[0];
        for(int i : a){
            max=Math.max(max,i);
            min=Math.min(min,i);
        }
        System.out.println("max:"+max+"  min:"+min);
        int k = max - min + 1;
        System.out.println("count array len:"+k);

        int c[] = new int[k];
        //先是count计数词频
        for(int i = 0; i < a.length; ++i){
            c[a[i]-min] ++;//优化过的地方,减小了数组c的大小,同时a[i]-min能保证c数组的第一个元素一定有元素的
            //因为必定存在min-min=0
        }
        System.out.println("count: "+Arrays.toString(c));
        //然后为了保持排序稳定,我们需要做一次累加操作
        //这样做的目的,是为了标记出原始数组里面的该元素,前面有几个元素,这个值
        //实际上就是其在原生数组里面的位置,如果有重复的元素,则会先会
        //放置最右边的元素,这样就能保证,排序的稳定性
        for(int i = 1; i < c.length; ++i){
            c[i] = c[i] + c[i-1];
        }

        System.out.println("sumCount:"+Arrays.toString(c));

        //存储最终的排序结果
        int b[] = new int[a.length];
        //这里必须从后向前遍历,只有这样出现重复的元素,才会保持顺序的把最后面的重复元素,永远放在最右边。
        //从而保证排序的稳定性
        //如果从前向后排序,重复元素的顺序,刚好相反,所以就不是稳定的算法,但如果不关注稳定性,那么结果还是正确的
        for (int i = a.length-1; i >=0 ; i--) {
             //减去min是为了优化存储空间,这样得到新的转换值,
             int pos=a[i]-min;
             int sumCount=c[pos];

            System.out.println(a[i]+" 在原数组的排序后的位置是: "+(sumCount-1));

            //把最终生层的排序值,放在新的数组里面返回
            b[sumCount-1]=a[i];
            c[pos]--; //如果有重复元素,位置需要从右向左放置,所以需要把sumCount的值-1

        }


        return b;
    }

其中关键的地方有两个:

第一,在于理解计算max和min之后,需要使用原数组每一个元素减去min的转换值统计词频,特定情况下能节省存储空间,这样做的另一个好处是可以兼容负数的情况,因为每一个元素减去最小值之后,结果必定是大于等于0

第二,在于理解为什么采用词频求和的方式+倒序遍历原始数组的方式,能保证排序算法的稳定性

理解了上面的两点,再来看优化后的计数排序就非常简单了,如果想证明计数排序的稳定性,可以参考我的github上的例子。

https://github.com/qindongliang/Java-Note

总结:

经典的计数排序分四个阶段:

1,找出数组里面的最大值和最小值

2,求出每个元素出现的词频(count)

3,遍历词频数组求和

4,反向遍历原始数组,进行目标数组填充,填充后的数组再遍历就是有序的。

如果不考虑算法的稳定性和负数情况及特定情况的浪费空间,那么只需要前面的2步就可以了,如果想要保证稳定性,那么需要经过这4步计算。具体证明计数排序的稳定性的例子,可以参考我的github上例子:

https://github.com/qindongliang/Java-Note/blob/master/src/main/java/sortalgorithm/countsort/ProveStableCountingSort.java

计数排序在特定的情况下,排序效率极高,但是如果排序的计数空间范围过大,而实际元素个数非常小的情况,效率就会非常差,比如,我只有3个元素,3,1,500000,这样的情况其实是不适合用计数排序的,这一点需要注意。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-10-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏你不就像风一样

让你一看就懂的快速排序算法(Java)

你也许会被快速排序的文章弄得迷迷糊糊,其实大体上去看,快速排序就一步:找个数做基准数,把小于它的数移到它左边,把大于它的数移到它右边。这句话是核心。然后我们只需...

1142
来自专栏nnngu

算法01 七大排序之:冒泡排序和快速排序

排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列;老师查看上课出勤情况时,会按学生学号顺序点名;高考录取时,会按成绩总分降序依次录取等。排序是数...

3727
来自专栏jojo的技术小屋

原 NaN和Infinity,null和u

作者:汪娇娇 日期:2016.10.10 看到这个标题,大家对这4个变量应该都不陌生,但若说起他们的差别或者是举个小栗子判断结果,估计就有点晕乎乎的了。 1、N...

3356
来自专栏程序员互动联盟

【编程基础】零基础学习Java之运算符

学习计算机编程语言都会遇到运算符这一知识点,运算符这个知识点是教怎么运用编程语言进行最基本的数据处理,下面就讲一下在Java语言中运算符是怎么回事。 1、算术运...

40910
来自专栏Python数据科学

十大经典排序算法(Python代码实现)

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

3001
来自专栏目标检测和深度学习

常用排序算法总结(2)

1374
来自专栏desperate633

深入理解python中的排序

进行一个简单的升序排列直接调用sorted()函数,函数将会返回一个排序后的列表:

861
来自专栏用户画像

Java int 最大值 最小值

从JDK1.0开始,Integer中就定义了MIN_VALUE和MAX-VALUE两个常量:

4941
来自专栏老九学堂

嘀 , 嘀嘀 ... 常用排序算法再总结

  这篇文章中再和小伙伴们来探讨一下常用的非比较排序算法:计数排序,基数排序,桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。

1263
来自专栏java一日一条

八大排序算法

(1)基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一...

741

扫码关注云+社区

领取腾讯云代金券