计数排序

计数排序, 基数排序, 桶排序等非比较排序算法,平均时间复杂度都是O(n). 这些排序因为其待排序元素本身就含有了定位特征,因而不需要比较就可以确定其前后位置,从而可以突破比较排序算法时间复杂度O(nlgn)的理论下限.

计数排序是最简单的特例,它要 求待排序元素是位于0到k之间的正整数 , 因而它是很特殊的情况,基本上没有特别的应用价值; 但是另一方面, 它又是基数排序的基础,或者说是一部分,所以简单的描述一下:

输入数组 A : 元素特征是 0-k的正整数,可以有重复值;

输出数组 B : 输出A的一个非减序列

中间数组 C : 大小是k, 它的i( 0<= i <= k)索引位置存储的是A元素集合中值是k的元素的个数有关.

 

算法的基本思想是:

• 统计A中元素的值的集合, 以A中元素的值为索引, 将值的个数填写到中间数组C的对应处.
• 对C从头开始自累加, 这样C中存储的就是, 当输入数组A中的值为当前索引时, 它前面的元素数量(包含重复元素).
• 将C依次输出到输出数组B中.

Java实现代码：

 

public static int[] countSort(int[] A,int max){
		int[] C = new int[max+1];
		int[] B = new int[A.length];
		for(int i:A){
			C[i]+=1;
		}
		for(int i=1;i=0;--i){
			B[C[A[i]]-1] = A[i];
			C[A[i]]-=1;
		}
		return B;
	}

测试代码：

public static void main(String[] args) {
		int N = 1000;
		int[] A =new int[100];
		Random r = new Random(System.currentTimeMillis());
		for(int i=0; i<A.length; ++i){
			A[i] = r.nextInt(N);
		}
		int max=Integer.MIN_VALUE;
		for(int i:A){
			max = (i>max)?i:max;
		}
		System.out.println("输入数组元素：");
		System.out.println(Arrays.toString(A));
		int[] B = countSort(A,max);
		System.out.println("输出数组元素：");
		System.out.println(Arrays.toString(B));
		Arrays.sort(A);
		if(Arrays.equals(A, B)){
			System.out.println("Correct!!!");
		}else
			System.out.println("Error???");
		
	}