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 stubint[] A={1,5,2,10,65,23,31};int length=A.length;int digit=10;//最大位数，这里为十位，它的作用是在向桶存放数据的时候构造一个映射，这里的映射条件是A[i]/digitnew BucketSort(A,length,10);}}