2012/3/31----计数排序

计数排序的核心思想是：对需要排序的数组A，计算出A中各个元素在排序后的数组B中的位置，然后在把A中的数值存放到B中相应的位置。

这里最重要的步骤就是对A中每一个元素进行计算，算出这个元素所在的位置。

下面就是详细代码：

/*
 * 计数排序算法的java实现
 * @version 1.0 2012/3/31
 * @author akon
 */
package com.akon405.www;

public class CountingSort {
	public  CountingSort(int[] A,int lenght,int largest){
		
		int[] temp = new int[largest+1];//创建一个临时数组，这个数组有两个用处
		int i;
		int[] B=new int[lenght];
		for(i=0;i<=largest;i++){
			temp[i]=0;
		}
		for(i=1;i<A.length;i++){
			temp[A[i]]++;//计算出A[i]的个数，把个数存在temp[A[i]]中
		}
		for(i=1;i<=largest;i++){
			temp[i]=temp[i]+temp[i-1];//计算出<=i的个数，存放在temp[i]中
		}
		for(i=lenght-1;i>=0;i--){
			B[temp[A[i]]]=A[i];//temp[A[i]]为在数组A中，小于等于A[i]的个数
			temp[A[i]]--;//个数减1
		}
		//输出排序的结果
		for(i=0;i<lenght;i++){
			System.out.print(B[i]+",");
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A={1,2,3,9,4,7,5,2,8};
		int large=9;
		int lenght=A.length;
		System.out.print("排序结果：");
		new CountingSort(A,lenght,large);
		
	}

}