计数排序

计数排序是一种特殊的排序算法,算法效率是线性的,最大的特点是不需要比较…

认识计数排序

计数排序是一种典型的不需要比较的排序方法,它的算法效率高于基于比较的排序算法的效率。计数排序是一种稳定的排序算法。

简单计数排序

计数排序将待排元素值定义为数组下标,用数组对应的值表示该下标(元素)出现的次数,最后将遍历数组即可得到有序的元素。

比如有一组数[4,2,5,1,2,2,4,5,6],由于需要将元素值转换为数组下标,所以需要一个新的数组counting,长度为元素最大值+1,以保证不会越界,转换之后的counting数组如下所示(下标表示元素值,数组存储的值表示该值出现的次数):
1

最后只需要顺序地将数组第i个元素输出counting[i]次即可(升序)。

以上是计数排序的基本思想。代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void simpleCountingSort(int[] values, boolean asc){
int maxValue=Tools.getMax(values); //获得最大元素
int[] counting=new int[maxValue+1];
int i,index=0;
for(i=0;i<values.length;i++){
counting[values[i]]++;
}
for(i=0;i<counting.length;i++){
for(int j=0;j<counting[i];j++){
values[asc?index++:values.length-(index++)-1]=i;
}
}
}

以上计数排序存在缺陷;如果遇到[90,99,95,94,95]这样一组数,就需要申请一个100长度的数组空间,而前90个空间都是毫无用处的,针对这样的问题对计数排序进行了改进。

改进的计数排序

由于一组数的同时减去一个相同的值之后它们的相对大小并无变化,这就是计数排序的改进思路。将一组数同时减去最小值,得到一组新的数,对新得到的数进行简单计数排序,最后再将排序的结果同时加上最小值。

比如[90,99,95,94,95]这组数,首先变成[0,9,5,4,5],然后进行排序[0,4,5,5,9],再加上90,得到最后的结果[90,94,95,95,99]。
2

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
public static void countingSort(int values[],boolean asc){
int minValue=Tools.getMin(values);
int[] subMin=new int[values.length];
for(int i=0;i<values.length;i++){
subMin[i]=values[i]-minValue;
}
simpleCountingSort(subMin,asc);
for(int i=0;i<values.length;i++){
values[i]=subMin[i]+minValue;
}
}

具有记忆功能的计数排序

计数排序最大的特点在于不需要比较,通过出现的次数决定元素的排序,所以当遇到重复元素时,根本无法区别两个元素。

比如有下面的一组键值对:
[“A”:90,”B”:99,”C”:95,”D”:94,”E”:95]

虽然有两个95,但是它们是有区别的,上面所提的方法无法区分是C还是E的95;所以我们对改进的计数算法再进行一些优化:

首先还是要得到counting数组
3

然后从第i(i>0)个元素开始,执行counting[i]+=counting[i-1]操作,最后得到的数组如下:
4

其中counting[9]=5表示,99应该排在第5位(升序最后一位)。

如何得到最后的排序结果?比如(A,90),90对应下标0,应该排在第1位,所以最后的结果数组的第一个元素是90,然后将counting[0]=counting[0]-1
5

再看(B,99),99对应9,排在第5位,然后再将counting[9]=counting[9]-1;以此类推,直到原始数据遍历完成即可。(如果要降序排序,只需要将排在的位数反过来即可)

实际上,执行counting[i]+=counting[i-1]操作就是为了记录各元素值的排序的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int[] memoryCountingSort(int[] values,boolean asc){
int maxValue=Tools.getMax(values);
int minValue=Tools.getMin(values);
int[] counting=new int[maxValue-minValue+1];
int i;
for(i=0;i<values.length;i++){
counting[values[i]-minValue]++;
}
for(i=1;i<counting.length;i++){
counting[i]+=counting[i-1];
}
int[] result=new int[values.length];
for(i=0;i<values.length;i++){
//请仔细斟酌这一句话
result[asc?(counting[values[i]-minValue]--)-1:values.length-(counting[values[i]-minValue]--)]=values[i];
}
return result;
}

总结

以上就是计数排序的基本思想与改进,最后简单的总结一下计数排序:

  • 计数排序是一种稳定的,线性时间的排序算法,不需要比较
  • 计数排序只能对整数排序,因为数组下标只能是整数
  • 计数排序受数据本身的局限性,只适合数据值大小集中的情况
smartpig wechat
扫一扫关注微信公众号
0%