(十八）排序算法-计数排序

1 基本介绍

1.1 概述

计数排序是一个非基于比较的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。这是一种牺牲空间换取时间的做法。

排序步骤：

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

1.2 算法详解

下面通过图解的方式了解计数排序的思想。

1. 第一次遍历序列，找出序列中的最大值以及最小值，然后根据最大值MAX与最小值MIN创建一个MAX-MIN+1长度的数组。为什么创建这样长度的数组呢？因为只有创建了这样长度的数组，MIN-MAX区间内的每个元素才有对应的位置进行存放，如下图所示。

2. 第二次遍历序列，每次遍历一个元素都将该元素所对应的区间数组对应的位置进行+1操作，这个步骤其实就是计数排序的核心----计数。遍历结束之后，区间数组中的元素值就代表相应元素出现的次数，如下图所示。

3. 最后一步就只需要按照区间数组中的次数一次将该元素打印出来即可。如下图所示。
   

了解完计数排序的基本思想之后，分析一下计数排序算法的一些特点：

• 计数排序是稳定的 ，这个大家应该能很明显的看出来，因为计数排序本身并不是基于比较的算法。
• 计数排序需要的额外空间比较大，这个大家很明显的看出来，并且空间浪费的情况也会比较严重，因为一旦序列中MAX与MIN的差距过大，那么需要的内存空间就会非常大。并且假如序列中的元素都是散布在一个特定的区间内，那么内存空间浪费的情况也会非常明显。

算法图解：

2 代码实现

/*** 计数排序*/
public class CountSort {public static void main(String[] args) {int []num ={7,4,9,3,2,1,8,6,5,10};long startTime=System.currentTimeMillis();int min=Integer.MAX_VALUE;int max=Integer.MIN_VALUE;//先找出数组中的最大值与最小值for(int i=0;i<num.length;i++) {if(num[i]<min)min=num[i];if(num[i]>max)max=num[i];}//创建一个长度为max-min+1长度的数组来进行计数int []figure=new int [max-min+1];for(int i=0;i<num.length;i++) {//计算每个数据出现的次数figure[num[i]-min]++;}int begin=0;//创建一个新的数组来存储已经排序完成的结果int []num1=new int [num.length];for(int i=0;i<figure.length;i++) {//循环将数据pop出来if(figure[i]!=0) {for(int j=0;j<figure[i];j++) {num1[begin++]=min+i;}}}System.out.println("数据范围:"+min+"~"+max);System.out.println("计数结果:  ");for(int i=0;i<num.length;i++)System.out.println("         "+num[i]+"出现"+figure[num[i]-min]+"次");System.out.print("排序结果:  ");for(int i=0;i<num1.length;i++)System.out.print(num1[i]+"   ");System.out.println();long endTime=System.currentTimeMillis();System.out.println("程序运行时间： "+(endTime-startTime)+"ms");}}

3 复杂度分析

• 时间复杂度
  计数排序很明显是一种通过空间来换时间的算法,因为我们可以很明显的看到计数排序需要三次遍历,两次遍历我们的原序列,第三次是遍历我们的区间数组.那么很明显时间复杂度一定是线性级别的但是因为第三次遍历的并不是我们的原序列,而是我们的区间数组,所以时间复杂度并不是我们的平常的O(n),而是应该加上我们遍历区间数组的时间,假设我们的区间数组长度为k的话,那么我们的时间复杂度就是O(n+k)

• 空间复杂度
  上面我们已经说过了,计数排序本身就是一个通过空间来换取时间的算法,所以很明显他的空间复杂度就会很高.并且这个空间复杂度主要就取决于我们区间数组的长度,所以假设我们的区间数组长度为k的话,那么我们的空间复杂度就为O(k)