《啊哈！算法》学习笔记之桶排序

时间复杂度：O(M+N)

M:桶的个数（也是该数值的最大数） N:待排序个数

Java实现

随便输入N个不大于M的数字，然后从小到大输出：（从大到小，作一下小修改即可）

    public static void main(String[] args) {
        int M= 100;
        int N = 5;
        int[] array = new int[M+ 1];
        Scanner scan = new Scanner(System.in);
        int in = 0;
        for (int i = 0; i < N; i++) {
            in = scan.nextInt();
            array[in] = array[in] + 1;
        }

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i]; j++) {
                System.out.println(i);
            }
        }
    }

个人总结

这种算法适合于范围比较小的排序，并且是需要知道输入的最大值。不然就不适用了。