桶排序概述与实现思路

桶排序的思想近乎彻底的分治思想。假设现在需要对一百万个数进行排序。我们可以将其等长地分到100个虚拟的“桶”里面，这样，平均每个桶只有10000个数。如果每个桶都有序了，则只需要依次输出为有序序列即可。具体思路是这样的：

1.将待排数据按一个映射函数f(x)分为连续的若干段。理论上最佳的分段方法应该使数据平均分布；实际上，通常采用的方法都做不到这一点。显然，对于一个已知输入范围在【0，10000】的数组，最简单的分段方法莫过于x/m这种方法，例如，f(x)=x/100。

“连续的”这个条件非常重要，它是后面数据按顺序输出的理论保证。

2.分配足够的桶，按照f(x)从数组起始处向后扫描，并把数据放到合适的桶中。对于上面的例子，如果数据有10000个，则我们需要分配101个桶（因为要考虑边界条件：f(x)=x/100会产生【0，100】共101种情况），理想情况下，每个桶有大约100个数据。

3.对每个桶进行内部排序，例如，使用快速排序。注意，如果数据足够大，这里可以继续递归使用桶排序，直到数据大小降到合适的范围。

4.按顺序从每个桶输出数据。例如，1号桶【112，123，145，189】，2号桶【234，235，250，250】，3号桶【361】，则输出序列为【112，123，145，189，234，235，250，250，361】。

代码实现：

public void bucketSort(int[] arr) {

// 1.求数组元素最大值与最小值。利用两者的差值进行分桶

int max = arr[0], min = arr[0];

for (int i = 0; i < arr.length; i++) {

max = (arr[0] > max) ? arr[0] : max;

min = (arr[0] < min) ? arr[0] : min;

}

int bucketNum = (max - min) / arr.length + 1;

// 2.定义一个存放桶的二维数组大桶存储桶的索引值小桶存储元素

Integer[][] bucketArray = new Integer[bucketNum][arr.length];// Integer初始为null,以与数字0区别。

for (int i = 0; i < arr.length; i++) {

int quotient = arr[i] / bucketNum;

for (int j = 0; j < arr.length; j++) {

if (bucketArray[quotient][j] == null) {

bucketArray[quotient][j] = arr[j];

break;

}

}

}

// 小桶排序（可以定义一个临界值，当小于这临界值用插入排序，大于用快速排序）

for (int i = 0; i < bucketArray.length; i++) {

// insertion sort

for (int j = 0; j < bucketArray[i].length; j++) {

if (bucketArray[i][j] == null) {

break;

}

int value = bucketArray[i][j];

int position = j;

while (position > 0 && bucketArray[i][position - 1] > value) {

bucketArray[i][position] = bucketArray[i][position - 1];

position--;

}

bucketArray[i][position] = value;

}

}

// 输出

int index = 0;

for (int i = 0; i < bucketArray.length; i++) {

for (int j = 0; j < bucketArray.length; j++) {

if (bucketArray[i][j] != null) {

arr[index] = bucketArray[i][j];

index++;

} else {

break;

}

}

}

}

实现难点

上面的代码并不长，但是却不好写。我在实现过程中主要遇到了以下问题：

1.最重要的问题：如何得知每个小桶需要多大？

显然，N个数平均分到M个桶，每个桶的容量应该是N/M，但实际数据不可能这么平均。解决办法无非是增加桶的容量。那么，我们应该增加到多少？

方案一：设定一个固定比例，例如使用10倍于平均的容量。这在很多时候能够解决问题，但遇到极端数据的时候容易出现问题。

方案二：极端增加空间大小，使得每个桶固定装一个数，这需要限制输入数据不重复。但是，如果输入数据没有范围限制，我们必须申请Integer.MAX_VALUE字节数据，而这必然会导致内存过大，引发Requested array size exceeds VM limit异常。但如果我们知道其数据范围，例如[1,100000]，则是可以接受的方案。并且这样可以省去排序的步骤，可以达到线性复杂度，效率很高。

方案三：也就是示例中的代码，实际上性能并不好。它是把每个小桶都做到和原始数组一样大，以牺牲很多空间来换取算法在极限情况下的健壮性。

2.如何克服Java数组的初始值？

如果是数值型数组，在分桶的时候容易由于创建数组时系统赋予的0值而给排序造成混乱，干扰结果。这里有两种情况：

A：如果输入数据明确不为零，则所受影响不大。只需要在输出和排序时注意判断，排除0值就行了。

B：如果数据可能为零，例如上述代码，这里的解决办法是申请Integer数组。由于系统初始值为null，我们可以更明确地绕开0值。

算法性能/复杂度

桶排序的时间复杂度可以从每一步分开分析。

1.分桶的过程，遍历每个元素、计算f(x)，将x放到桶中，共3n次计算，显然是O(n)复杂度；

2.最后输出也是O(n)复杂度；

3.关键是小桶内排序的过程：即使使用先进的比较排序算法，也不可绕开O(n㏒n)的下限。因此，每个小桶的内部复杂度为n(k㏒k)，总得复杂度为∑(ki*㏒ki)[i=1...m]，其中m为桶的个数，ki为每个桶的元素数。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此，有两种方法：

1）使用更为平均的划分，使得不至于某个小桶的数据极多；

2）使用更多的桶，以减少每个桶数据的数量。极限状况下，每个桶只有一个数据，这样就完全没有比较操作。但是，在数据极多的情况下，这样是非常不现实的，会造成严重的空间消耗。这时候就需要权衡时空间复杂度了。

总结起来，设数据共有N个，桶有M个，则桶排序平均复杂度为：

O(N)+O(N)+O((N/M)*㏒(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

最优情形下，桶排序的时间复杂度为O(n)。

桶排序的空间复杂度通常是比较高的，额外开销为O(N+M)（因为要维护M个数组的引用）。

算法稳定性

可以看出，在分桶和从桶依次输出的过程是稳定的。但是，由于我们在第3步使用了其他算法，所以，桶排序的稳定性依赖于这一步。如果我们使用了快排，显然，算法是不稳定的。

算法适用场景

桶排序在数据量非常大，而空间相对充裕的时候是很实用的，可以大大降低算法的运算数量级。此外，在解决一些特殊问题的时候，桶排序可能会起到意想不到的结果