简单桶排序

这是简化版的桶排序，真实的桶排序要更复杂些。

一个班有5个学生，举行了一次考试，总分是10分，5个学生的成绩分别是 5、6、2、0、5。现在需要按成绩从最低分到最高分排序。
成绩分布的所有可能是0分到10分共11种可能（就好比11个桶），使用一维数组 a[0]~a[10] 表示各个分数的人数，比如 a[5] = 2 表示成绩为5分的有2个学生。先置其初始值为0，表示暂时还没有学生得到过相应的分数，第一个学生是5分，记 a[5] = a[5] + 1，第二个学生是6分，记 a[6] = a[6] + 1，依次类推。得出的结果如下：

a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]
1	0	1	0	0	2	1	0	0	0	0

从0到10开始遍历数组 a，该项的值为多少则打印多少次，比如 a[5] = 2，打印2次5，a[3] = 0 则不打印。代码实现如下：

• 简单桶排序

public class SimpleBucketSort {
    public static void main(String[] args) {
        int[] data = new int[] {5, 6, 2, 0, 5};
        sort(data, 10);
    }

    public static void sort(int[] data, int max) {
        int[] bucket = new int[max + 1];
        for (int i = 0, size = data.length; i < size; i++) {
            bucket[data[i]]++;
        }
        for (int i = 0, size = max + 1; i < size; i++) {
            for (int j = 0; j < bucket[i]; j++) {
                System.out.println(i);
            }
        }
    }
}

运行结果：
0
2
5
5
6

再来看看该算法的时间复杂度，第一个 for 循环了 M 次（M为待排序的个数），第二个 for 循环里嵌套了一个 for 循环，循环了 N + M 次（N为桶的个数），所以整个算法的时间负杂度为 O(2M+N)=O(M+N)。

顺便说说在写这个简单桶排序时候的一些思考。桶排序的一个问题在于桶的数量为多少更为合适，假设需要排序的数的范围是 0~1000，但是待排序的数只有5个，比如为 200、212、226、207、210。这种情况下，需要创建1001个桶，显然存在很大的空间浪费。想到的第一个解决办法是使用待排序的最大数减去待排序的最小数，即只创建 226 - 200 + 1 = 27 个桶。但是这样又带来了四个新问题，一是需要额外的基数来对应桶的真实位置，比如27个桶，构造一维数组像这样 int[] bucket = new int[27]，但是这里的 bucket[0] 其实并不是表示数值 0，而是表示数值 200，这样的话，就需要一个额外的基数 200 来加上当前的索引才能表示真实的数值，这增加了算法的复杂性；二是需要额外地先计算出待排序数组的最大值和最小值，这增加了计算量，还可能需要引入其他的算法来完成这个操作；三是并没有从根本上解决问题，如果待排序数分布为 50、0、1000、564、877，那么同样需要1001个桶；四是违背了笔者写这篇文章的初衷，这篇文章是入门级的，旨在对简单桶排序有一个简单了解，突出的是简单桶排序本身，而并不想让太多其他次要的东西所干扰。基于上述四点考虑，就放弃了这种做法，之所以在这里提出来，是希望能对简单桶排序有一个更清晰的认识。