`

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

    博客分类:
  • java
阅读更多

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


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


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

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

Java代码  收藏代码
  1. ```  
  2.     public static void  simpleCountSort(){  
  3.         int nums[]={2,1,0,1};  
  4.   
  5.         int maxNum=2;  
  6.   
  7.         int storeArray[]=new int[maxNum+1];  
  8.   
  9.         //词频计数  
  10.         for(int i=0;i<nums.length;i++){  
  11.             storeArray[nums[i]]++;  
  12.         }  
  13.   
  14.         System.out.println("==============排序后==============");  
  15.   
  16.         int ndx=0;  
  17.         //遍历计数后的词频数组  
  18.         for (int i = 0; i <storeArray.length ; i++) {  
  19.             //对于每个index的值进行循环,输出,因为有可能重复  
  20.             while (storeArray[i]>0){  
  21.                 nums[ndx]=i;//把词频数组的值,放回原数组里面,  
  22.                 ndx++;//替换一个数,就索引自增  
  23.                 storeArray[i]--;//词频减1,防止死循环  
  24.             }  
  25.         }  
  26.   
  27.   
  28.         System.out.println(Arrays.toString(nums));  
  29.   
  30.   
  31.   
  32.     }  
  33. ```  


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

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

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

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

优化后的代码如下: 

Java代码  收藏代码
  1. ```  
  2.   public static int[] countSort(int []a){  
  3.         //使用最大值和最小值的方式是一种优化的计数排序  
  4.         //可以兼容负数的情况,同时能减少存储的空间,比如最大数是100,但实际上只有90-100这10个数字  
  5.         //所以仅仅需要10个存储空间即可  
  6.         int max = a[0], min = a[0];  
  7.         for(int i : a){  
  8.             max=Math.max(max,i);  
  9.             min=Math.min(min,i);  
  10.         }  
  11.         System.out.println("max:"+max+"  min:"+min);  
  12.         int k = max - min + 1;  
  13.         System.out.println("count array len:"+k);  
  14.   
  15.         int c[] = new int[k];  
  16.         //先是count计数词频  
  17.         for(int i = 0; i < a.length; ++i){  
  18.             c[a[i]-min] ++;//优化过的地方,减小了数组c的大小,同时a[i]-min能保证c数组的第一个元素一定有元素的  
  19.             //因为必定存在min-min=0  
  20.         }  
  21.         System.out.println("count: "+Arrays.toString(c));  
  22.         //然后为了保持排序稳定,我们需要做一次累加操作  
  23.         //这样做的目的,是为了标记出原始数组里面的该元素,前面有几个元素,这个值  
  24.         //实际上就是其在原生数组里面的位置,如果有重复的元素,则会先会  
  25.         //放置最右边的元素,这样就能保证,排序的稳定性  
  26.         for(int i = 1; i < c.length; ++i){  
  27.             c[i] = c[i] + c[i-1];  
  28.         }  
  29.   
  30.         System.out.println("sumCount:"+Arrays.toString(c));  
  31.   
  32.         //存储最终的排序结果  
  33.         int b[] = new int[a.length];  
  34.         //这里必须从后向前遍历,只有这样出现重复的元素,才会保持顺序的把最后面的重复元素,永远放在最右边。  
  35.         //从而保证排序的稳定性  
  36.         //如果从前向后排序,重复元素的顺序,刚好相反,所以就不是稳定的算法,但如果不关注稳定性,那么结果还是正确的  
  37.         for (int i = a.length-1; i >=0 ; i--) {  
  38.              //减去min是为了优化存储空间,这样得到新的转换值,  
  39.              int pos=a[i]-min;  
  40.              int sumCount=c[pos];  
  41.   
  42.             System.out.println(a[i]+" 在原数组的排序后的位置是: "+(sumCount-1));  
  43.   
  44.             //把最终生层的排序值,放在新的数组里面返回  
  45.             b[sumCount-1]=a[i];  
  46.             c[pos]--; //如果有重复元素,位置需要从右向左放置,所以需要把sumCount的值-1  
  47.   
  48.         }  
  49.   
  50.   
  51.         return b;  
  52.     }  
  53. ```  


其中关键的地方有两个: 

第一,在于理解计算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/sort_algorithm/count_sort/ProveStableCountingSort.java 


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

 

 

 

本文转自:http://qindongliang.iteye.com/blog/2431975

分享到:
评论

相关推荐

    计数排序算法的C语言实现

    计数排序算法的效率主要取决于输入数据的特性,因此在实际应用中,需要根据具体情况进行选择。 总结来说,计数排序是一种非常特殊的排序算法,它通过预处理得到每个元素出现的次数,再利用这些信息直接确定每个元素...

    计数排序算法实例

    在"算法导论"这本书中,计数排序被作为经典算法介绍,用于教学和理解排序算法的不同机制。VC.60Test实例则可能是一个使用Visual C++ 6.0编写的程序,用于演示和验证计数排序的正确性。这个压缩包中的"CountSort"文件...

    排序算法(C语言实现)

    这些C语言实现的排序算法对于学习和理解排序算法的工作原理非常有帮助。通过阅读和分析代码,可以深入理解每种算法的内部机制,这对于提升编程技能和优化算法设计至关重要。在实际应用中,根据数据特性和性能需求,...

    排序算法: 冒泡排序,桶排序,计数排序,堆排序,插入排序,合并排序,快速排序,基数排序,选择排序,希尔排序 实现语言: C++

    本文将详细探讨十种经典的排序算法在C++中的实现,分别是冒泡排序、桶排序、计数排序、堆排序、插入排序、合并排序、快速排序、基数排序、选择排序和希尔排序。 1. **冒泡排序**:冒泡排序是最简单的排序算法之一,...

    各种常用排序算法的C语言实现

    在编程领域,排序算法是计算机科学中的核心概念,它们用于组织和优化数据处理。C语言是一种广泛应用的编程...通过学习这些C语言实现,可以帮助开发者深入理解排序算法的工作原理,从而在实际问题中选择合适的排序方法。

    排序算法的实现

    在编程领域,排序算法是计算机科学中的核心概念,特别是在数据处理和数据分析方面。本文将详细介绍在C语言中实现的八种排序算法,并探讨每种...理解并熟练掌握这些排序算法,对于提升编程能力和解决实际问题至关重要。

    常用各种排序算法Java的实现_差不多了__.rar

    通过学习和实践这些Java实现,开发者可以深入理解排序算法的工作原理,提升编程能力,并能根据实际需求选择合适的排序方法。 在实际开发中,了解并熟练掌握这些排序算法对于优化程序性能、解决复杂问题具有重要意义...

    实现所有经典排序算法汇总

    在计算机科学领域,排序算法是数据处理中至关重要的一部分,它涉及到如何有效地重新排列一组数据,使其按照特定标准(如升序或降序)排列...学习和理解这些经典的排序算法对于提升编程能力、优化算法性能具有重要意义。

    经典排序算法(C语言实现).zip

    本项目“经典排序算法(C语言实现)”提供了C语言版本的多种常见排序算法实现,对于学习和理解排序算法有极大的帮助。下面我们将深入探讨这些排序算法的核心原理及其C语言实现。 1. 冒泡排序(Bubble Sort) 冒泡...

    总结了各种排序算法,并用C++代码实现,并有演示

    本资源"总结了各种排序算法,并用C++代码实现,并有演示",提供了丰富的学习材料,包括不同类型的排序算法以及它们的C++实现,还有可能的可视化演示,帮助理解每种算法的工作原理。 首先,让我们逐一了解常见的排序...

    经典的排序算法C++实现大全

    在编程领域,排序算法是数据结构与算法课程中不可或缺的一部分,它们用于组织和优化数据的存储,以便快速访问和检索。本资源“经典的排序算法C++实现大全”提供了九种不同的排序算法,每种都有C++语言的实现,并且...

    常用排序算法java演示

    7. **计数排序(Counting Sort)、桶排序(Bucket Sort)和基数排序(Radix Sort)**:这三种排序算法属于非比较型排序,不依赖于元素间的比较,而是基于特定的特性,如元素的范围、分布等。Java中实现这类排序通常...

    用javascript实现的十大排序算法详解

    本篇文章将深入探讨如何使用JavaScript实现十大经典排序算法,帮助开发者更好地理解和运用这些算法。 1. 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序方法,通过重复遍历待排序的数组,比较相邻元素并交换...

    用C实现了排序算法中的插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、桶排序、基数排序

    在这份文档中,我用C语言实现了排序算法的多种方法,包括插入排序、选择排序、...排序算法是计算机科学中非常重要的基础知识,深入研究和理解这些算法的原理和实现,将有助于我们更好地解决实际问题和提升编程能力。

    三种线性排序算法Java实现

    本资源提供的Java实现包括了三种线性排序算法:桶排序(Bucket Sort)、基数排序(Radix Sort)和计数排序(Counting Sort)。这三种算法在特定条件下可以达到线性的平均或最好时间复杂度,效率相对较高。 1. **桶...

    内部排序算法的实现与比较

    了解这些排序算法的实现原理、时间复杂度和适用场景是十分关键的。例如,快速排序通常在实际应用中表现最好,而归并排序因其稳定性而在处理大数据集时受到青睐。学习这些算法可以帮助开发者根据具体需求选择合适的...

    排序算法JAVA实现,eclipse+txt

    在IT领域,排序算法是计算机科学中的核心概念,特别是在数据结构和算法分析中。Java作为一种广泛应用的编程语言,提供了丰富的...这个资料包中的Java实现和Eclipse工程,可以帮助开发者深入理解和实践这些排序算法。

Global site tag (gtag.js) - Google Analytics