2012/4/3----桶排序

清明假期第一天休息，今天继续来一个算法。今天写的是桶排序的算法实现：这个算法的思想很简单，就是把待排序的数据根据一定的映射条件分布到若干的“桶”中，然后对每个“桶”中的数据进行排序，最后再把各个桶进行合并就可以得到我们排序顺序了。

下面就是具体实现过程，里面有详细的注释：

/*
 * 桶排序的java实现
 * @version 1.0 2012/4/3
 * @author akon
 */
package com.akon405.www;
public class BucketSort {
	public BucketSort(int[] A,int length,int digit){
		int[][] B=new int[10][length];
		int[] cout=new int[10];
		int i;
		int j;
		//构造一个二维数组B，用来存放A中的数据,这里的B相当于很多桶，B[i][]代表第i个桶
		for(i=0;i<length;i++){
			B[A[i]/10][cout[A[i]/10]]=A[i];//B[0][]中存放A中进行A[i]/10运算后高位为0的数据，同理B[1][]存放高位为1的数据
			cout[A[i]/10]++;//用来计数二维数组中列中数据的个数，也就是桶A[i]中存放数据的个数
		}
		
		//下面使用直接插入排序对这个二维数组进行排序,也就是对每个桶进行排序
		for(i=0;i<10;i++){
			//下面是对具有数据的一列进行直接插入排序，也就是对B[i][]这个桶中的数据进行排序
			if(cout[i]!=0){
				for(j=0;j<cout[i];j++){
					int key=B[i][j];
					int n=j-1;
					while(n>=0&&B[i][j]<B[i][j-1]){
						B[i][j]=B[i][j-1];//向前移动一位，直到key>B[i][j-1]或者确定key为最小值的时候才结束
						j--;
					}
					B[i][j]=key;
				}
			}
		}
		
		//打印输出这个二维数组，就可以得到排序过后的顺序
		for(i=0;i<10;i++){
			if(cout[i]!=0){
				for(j=0;j<cout[i];j++){
					System.out.println(B[i][j]+",");
				}
					
			}
			
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A={1,5,2,10,65,23,31};
		int length=A.length;
		int digit=10;//最大位数，这里为十位，它的作用是在向桶存放数据的时候构造一个映射，这里的映射条件是A[i]/digit
		new BucketSort(A,length,10);
	}

}