桶排序 (Bucket sort)

桶排序 (Bucket sort)：将数据分配到有限数量的有序桶里。

对如下一组数进行排序：3，5，1，4，12，18，19，20，9，3，15，7，0。（数据大小在0到20之间）

排序代码如下：

public void bucketSort() {
    int[] befArrays = {3, 5, 1, 4, 12, 18, 19, 20, 9, 3, 15, 7, 0};
    int[] buckets = new int[21];
    for (int i=0; i<befArrays.length; i++) {
        buckets[befArrays[i]]++;
    }

    for (int i=0; i<buckets.length; i++) {
        if (buckets[i]==0) {
            continue;
        } else {
            for (int j=0; j<buckets[i]; j++) {
                System.out.printf(i + "\t");
            }
        }
    }
}

桶排序对要排序的数据的有非常严格的要求。主要有以下两点：
首先，要排序的数据需要很容易就能划分成所需要的桶，并且，桶之间有着大小顺序。
其次，数据在桶之间的分布是比较均匀的。如果数据分配到了桶里，有些桶里非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情的时候，如果数据都被分到同一个桶里，那就失去了该算法的意义。

总之，桶排序非常简单有效。但是使用场景极其有限。作为一个入门级的算法知识，能让我们感受到编程的快乐。桶排序还是相当推荐的。