计数排序-Java

计数排序是一种非基于比较的排序算法。它的优势在于一定范围内的整数排序时，它的复杂度为O(n+k)，快于任何比较排序，其中n是待排序个数，k为数的范围。因此，基数排序本来就是针对事先对待排序数据有所了解，即这些数是如何分布的，如果有负数或者有少量数极大，就不适合使用计数排序。

public class CountintSort {
	public static int[] CountintSort(int[] a){
		int[] b=new int[a.length];
		int max=a[0],min=a[0];
		for(int i=0;i<a.length;i++){
			if(a[i]>max)
				max=a[i];
			if(a[i]<min)
				min=a[i];
		}
		int k=max-min+1;
		int[] c=new int[k];
		for(int i=0;i<a.length;i++){
			c[a[i]-min]+=1;
		}
		for(int i=1;i<c.length;i++){
			c[i]=c[i]+c[i-1];
		}
		for(int i=a.length-1;i>=0;i--){
			b[--c[a[i]-min]]=a[i];
		}                                                                                                                                                                                                                                                                                                                                                                                                             
		return b;
	}
	public static void main(String[] args){
		int[] a={3,6,5,2,1,7,9,6,5};
		int[] b=CountintSort(a);
		for(int i=0;i<b.length;i++){
			System.out.print(b[i]+" ");
		}
	}
}