2012/4/3----桶排序 博客分类: 算法
程序员文章站
2024-03-25 09:57:28
...
清明假期第一天休息,今天继续来一个算法。今天写的是桶排序的算法实现:这个算法的思想很简单,就是把待排序的数据根据一定的映射条件分布到若干的“桶”中,然后对每个“桶”中的数据进行排序,最后再把各个桶进行合并就可以得到我们排序顺序了。
下面就是具体实现过程,里面有详细的注释:
/* * 桶排序的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); } }