算法——排序算法——计数排序

先来看一个问题：数组里有20个随机整数，取值范围是0—10，如何利用最快的速度将这20个整数从小到大排序。

在数据结构课程中，像这种排序一般都会使用快速排序，这些排序算法都是基于元素大小之间的比较。计数排序算法却比快速排序更快，但是只能用于一定范围内的整数排序，在取值范围不大的情况下效率大于O(nlogn)的排序。

思想：假设0-10这二十个数字是：9  0  9  2  3  6  7  8  9  5  10  10   3   5  1  4  9  9  7  1 

首先更具0—10的取值范围建立一个长度为11的数组a[ ]，数组里初始化元素的值全为0，数组的小标从0—10。现在开始对上面给出的20个整数进行遍历：

第一个整数是9，则在数组下标为9的元素的值加1，a[9]=1；

第二个整数是0，则在数组下标为0的元素的值加1，a[0]=1;

第三个整数是9，则在数组下标为9的元素的值加1，a[9]=2;

第四个整数是2，则在数组下标为2的元素的值加1，a[2]=1;

以此类推，最终得到的数组是：a[0]=1,  a[1]=2,  a[2]=1,  a[3]=2,  a[4]=1,  a[5]=2,  a[6]=1,  a[7]=2,  a[8]=1,   a[9]=5,  a[10]=2

如图所示： 

将这些元素从数组中遍历取出：0  1  1   2  3  3  4  5  5  6  7  7  8  9  9  9  9  9   10  10，输出的数列已经是有序的了。算法的时间复杂度为Ο(n+k),K为元素取值范围。

具体实现代码：

import java.util.Arrays;
 
 
public class countSort {
 
	/**
	 * @param args
	 */
	public static int[] countSort(int[] array){
		//定义数组的最大值
		int max = array[0];
		for(int i=1;i<array.length;i++){
			if(array[i]>max){
				max=array[i];
			}
		}
		//根据数组最大值确定统计数组的长度
		int[] countArray = new int[max+1];
		//遍历数组，把统计数组填上
		for(int i1=0;i1<array.length;i1++){
			countArray[array[i1]]++;
		}
		//遍历统计数组输出结果
		int index=0;
		int[] sortArray = new int[array.length];
		for(int j=0;j<countArray.length;j++){
             for(int v=0;v<countArray[j];v++){
            	 sortArray[index++]=j;
             }			
		}
		return sortArray;
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
           int[] array= new int[]{4,4,6,9,2,5,0,10,9,4,6,9,1,0};
           int[] sortArray=countSort(array);
           System.out.println(Arrays.toString(sortArray));
	}
 
}

输出结果：

这种做法有一些缺点，比如对如下数字排列：92,98,94,96,90,99,91  统计数组的长度会造成特别大的浪费。所以改进为统计数组的长度为最大值-最小值+1，也就是99-90+1=10，数组偏移量为数列的最小值90。

关于计数排序的实际应用优化请看下一篇博客。