9.13.1. 箱排序¶

设想过去一年里，你在支付各种账单时，只是把所有单据随手堆在某个角落里。现在一年结束了，你决定该按账单的用途（电话、电费、房租等）和日期把这些纸张整理一下。一个很自然的做法是在地板上腾出一些空间，然后一边翻看那堆纸张，一边把电话账单放进一堆，把电费账单放进另一堆，以此类推。一旦完成了账单到各堆的初始分配（一趟即可），你就可以相对快速地按日期对每一堆分别排序，因为每一堆都相当小。这就是 箱排序 背后的基本思想。

我们从一种特别简单的情形开始。考虑下面这段代码片段，用于对数字 0 到 \(n-1\) 的一个排列进行排序。

  for (i=0; i<A.length; i++)
    B[A[i]] = A[i];

Settings

Saving...
Server Error
Resubmit

这里用键值来确定记录在最终有序数组中的位置。这是 箱排序 最基本的例子，其中用键值把记录分配到各个箱中。这个算法极其高效，无论键的初始次序如何，总是花费 \(\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;
}

这个版本的箱排序可以排序任何键值落在 0 到 MaxKeyValue 范围内的记录集合。

Settings

Saving...
Server Error
Resubmit

所需的总工作量，就是把每条记录放入合适的箱、再把所有记录从箱中取出来所需的工作量。因此，我们需要对每条记录处理两次，总工作量为 \(\Theta(n)\) 。

这样的成本分析真的合理吗？实际上，最后那句话是 错的 ，因为它忽略了一个关键观察。把所有记录从箱中取出来，要求箱排序检查每一个箱，看它是否包含记录。因此，无论实际上有多少箱装有记录，算法都必须处理 MaxKeyValue 个箱。如果 MaxKeyValue 相对于 \(n\) 很小，那么这倒不算很大的开销。假设 MaxKeyValue \(= n^2\) 。在这种情况下，完成的总工作量为 \(\Theta(n + n^2) = \Theta(n^2)\) 。这导致一个糟糕的排序算法。而且随着 \(n\) 与 MaxKeyValue 之间差距的增大，这个算法会变得更糟。此外，较大的键范围需要一个大到无法接受的数组 B 。因此，即使是扩展后的箱排序，也只适用于有限的键范围。

对箱排序作进一步推广，会得到 桶排序 。在这里，每个箱（现在称为桶）关联的不只是一个键，而是一个键值范围。桶排序把记录分配到各个桶中，然后依靠某种其他排序技术对每个桶内的记录进行排序。希望在于，相对廉价的装桶过程只会把少量记录放进每个桶，这样对每个桶做一次"清理排序"就相对便宜。这在精神上类似于基数排序，后者以一种实用的方式扩展了箱排序的概念。