Bean3ai

前不久买了本刚出的新书《啊哈！算法》，打算把上面学到的东西搬到这儿来，与众分享。首先，桶排序。桶排序的基本思想是由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[]的作用是标记某个数出现的次数，然后依数组的下标的遍历(下标是已排好序的)将标记为非零的下标打印出来。