前不久买了本刚出的新书《啊哈!算法》,打算把上面学到的东西搬到这儿来,与众分享。首先,桶排序。桶排序的基本思想是由E.I Issac和B.C Singleton提出来的。下面是一段简化版的桶排序算法的实现。
import java.util.Scanner;
public class BinSort {
public static void main(String[] args){
final int NUMBERS_OF_ELEMENTS = 11;
int counts;
Scanner input = new Scanner(System.in);
//初始化桶
int[] bin = new int[NUMBERS_OF_ELEMENTS];
for(int i = 0; i < bin.length; i++)
bin[i] = 0;
//输入需要排序的数
System.out.println("输入需要排序(0-10)数的个数:\n");
counts = input.nextInt();
System.out.println("输入需要排序(0-10)的数:\n");
for(int i = 0; i < counts; ){
int num = input.nextInt();
//检查输入的数的合法性
if(num < 0 || num >= bin.length){
System.out.println("输入需在范围(0-10)内,请继续输入!\n");
}else{
bin[num]++;
i++;
}
}
//输出排序结果(从小到大)
System.out.println("排序结果:\n");
for(int i = 0; i < NUMBERS_OF_ELEMENTS; i++){
for(int j = bin[i]; j > 0; j--)
System.out.print(i + " ");
}
System.out.println();
//关闭Scanner
input.close();
}
}
上述程序可以实现counts个0-10的数从小到大的排序,数组bin[]的作用是标记某个数出现的次数,然后依数组的下标的遍历(下标是已排好序的)将标记为非零的下标打印出来。