13. 桶排序¶
13.1. 桶排序¶
设想过去一年里，你在支付各种账单时，只是把所有单据随手堆在某个角落里。 现在一年结束了，你决定该按账单的用途（电话、电费、房租等）和日期把这些 纸张整理一下。 一个很自然的做法是在地板上腾出一些空间，然后一边翻看那堆纸张，一边把 电话账单放进一堆，把电费账单放进另一堆，以此类推。 一旦完成了账单到各堆的初始分配（一趟即可），你就可以相对快速地按日期对 每一堆分别排序，因为每一堆都相当小。 这就是 桶排序 背后的基本思想。
我们从一种特别简单的情形开始。 考虑下面这段代码片段，用于对数字 0 到 \(n-1\) 的一个排列进行排序。
这里用键值来确定记录在最终有序数组中的位置。 这是 桶排序 最基本的例子，其中用键值把记录分配到 各个桶中。 这个算法极其高效，无论键的初始次序如何，总是花费 \(\Theta(n)\) 时间。 这远好于我们目前见过的任何排序算法的性能。 问题在于这个算法的用途有限，因为它只适用于 0 到 \(n-1\) 这些数字的 一个排列。
我们可以扩展这个简单版本的桶排序算法，使其更加有用。 由于桶排序必须对键值进行直接计算（而不像我们之前的排序算法那样， 只是询问两条记录中哪一条在前），我们将假定记录使用整数键类型。
最简单的扩展是允许键中出现重复值。
这可以通过把数组槽位变成任意长度的桶来实现，办法是把数组 B 变成
一个由链表构成的数组。
这样，所有键值为 \(i\) 的记录都可以放入桶 B[i] 中。
第二个扩展允许键范围大于 \(n\) 。
例如，一组 \(n\) 条记录的键可能落在 1 到 \(2n\) 的范围内。
唯一的要求是每个可能的键值在 B 中都有一个对应的桶。
我们假定已知可能的键范围在 0 到 MaxKeyValue 之间。
下面是扩展后的桶排序算法。
void binsort(int[] A) {
List[] B = new LinkedList[MaxKeyValue+1];
int item;
for (int i=0; i<=MaxKeyValue; i++)
B[i] = new LinkedList();
for (int i=0; i<A.length; i++) B[A[i]].append(A[i]);
int pos = 0;
for (int i=0; i<=MaxKeyValue; i++)
for (B[i].moveToStart(); (item = B[i].getValue()) != -1; B[i].next())
A[pos++] = item;
}
void binsort(Integer[] A) {
List[] B = new LinkedList[MaxKeyValue+1];
Object item;
for (int i=0; i<=MaxKeyValue; i++)
B[i] = new LinkedList();
for (int i=0; i<A.length; i++) B[A[i]].append(new Integer(A[i]));
int pos = 0;
for (int i=0; i<=MaxKeyValue; i++)
for (B[i].moveToStart(); (item = B[i].getValue()) != null; B[i].next())
A[pos++] = (Integer)item;
}
这个版本的桶排序可以排序任何键值落在 0 到 MaxKeyValue 范围内的
记录集合。
所需的总工作量，就是把每条记录放入合适的桶、再把所有记录从桶中取出来 所需的工作量。 因此，我们需要对每条记录处理两次，总工作量为 \(\Theta(n)\) 。
这样的代价分析真的合理吗？
实际上，最后那句话是 错的 ，因为它忽略了一个关键观察。
把所有记录从桶中取出来，要求桶排序检查每一个桶，看它是否包含记录。
因此，无论实际上有多少桶装有记录，算法都必须处理 MaxKeyValue 个桶。
如果 MaxKeyValue 相对于 \(n\) 很小，那么这倒不算很大的开销。
假设 MaxKeyValue \(= n^2\) 。
在这种情况下，完成的总工作量为 \(\Theta(n + n^2) = \Theta(n^2)\) 。
这导致一个糟糕的排序算法。
而且随着 \(n\) 与 MaxKeyValue 之间差距的增大，这个算法会变得更糟。
此外，较大的键范围需要一个大到无法接受的数组 B 。
因此，即使是扩展后的桶排序，也只适用于有限的键范围。
对桶排序作进一步推广，会得到 桶排序 。 在这里，每个桶（现在称为 bucket）关联的不只是一个键，而是一个键 值范围。 桶排序把记录分配到各个桶中，然后依靠某种其他排序技术对每个桶内的记录 进行排序。 希望在于，相对廉价的装桶过程只会把少量记录放进每个桶，这样对每个桶做 一次"清理排序"就相对便宜。 这在精神上类似于基数排序，后者以一种实用的方式扩展了桶排序的概念。
