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

时间复杂度：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);
        }
    }
}

个人总结

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