12.14. 基数排序¶
12.14.1. 基数排序¶
箱排序的主要问题是，当键范围很大时它表现不佳。幸运的是，有一种办法可以在仍然使用"把键值相近的记录装箱"这一思想的同时，让箱的数量保持较少、相关处理相对廉价。考虑一个键在 0 到 99 范围内的记录序列。如果我们有十个箱可用，可以首先用键值对 10 取模来把记录分配到箱中。这样，每个键都会被分配到与其最右边十进制数字相匹配的箱。然后我们可以 按顺序 从这些箱中取出记录，并根据它们最左边（十位）的数字重新分配到各箱中。我们约定，0 到 9 范围内的值，其最左边数字为 0。换句话说，用公式 A[i]/10 把数组 A 中的第 \(i\) 条记录分配到一个箱中。如果我们现在 按顺序 从各箱中收集这些值，结果就是一个有序线性表。我们可以在下面的可视化中看到这个过程。
在这个例子中，我们有 \(r=10\) 个箱，键值在 0 到 \(r^2-1\) 范围内。总计算量为 \(\Theta(n)\) ，因为我们查看每条记录和每个箱的次数都是常数。这相比简单箱排序是一个很大的改进——后者中箱的数量必须与键范围一样大。注意，这个例子使用 \(r = 10\) ，是为了让装箱计算易于可视化：记录先根据最右边的十进制数字、再根据最左边的十进制数字被放入箱中。只要按相应的进制来解释键值，任何数量的箱都可以奏效。这就是 基数排序 的一个例子，它之所以这样叫，是因为装箱计算基于键的 基数 或 进制 。这种排序算法可以推广到任意键数量和任意键范围。我们只需根据键的数字位，从最右边的数字位到最左边的数字位，把记录分配到各箱中。如果有 \(k\) 个数字位，那么这需要把键分配到箱中 \(k\) 次。
下面是一个把键放入箱中的练习。
12.14.2. 基于数组的基数排序¶
与归并排序一样，基数排序的高效实现也相当困难。具体来说，我们更希望对一个值的数组进行排序，而避免处理链表。如果我们知道每个箱中将有多少个值，那么就可以用一个大小为 \(r\) 的辅助数组来记录这些长度，并指导我们确定每个箱在输出数组中的起始位置。例如，如果在第一趟中 0 号箱将接收三条记录、1 号箱将接收五条记录，那么我们只需为 0 号箱保留数组的前三个位置，为 1 号箱保留接下来的五个位置。下面的实现正是采用这种做法。每一趟结束时，记录会被复制回原数组。
static void radix(int[] A, int k, int r) {
int[] B = new int[A.length];
int[] count = new int[r]; // Count[i] stores number of records with digit value i
int i, j, rtok;
for (i=0, rtok=1; i<k; i++, rtok*=r) { // For k digits
for (j=0; j<r; j++) { count[j] = 0; } // Initialize count
// Count the number of records for each bin on this pass
for (j=0; j<A.length; j++) { count[(A[j]/rtok)%r]++; }
// After processing, count[j] will be index in B for first slot of bin j.
int total = A.length;
for (j=r-1; j>=0; j--) { total -= count[j]; count[j] = total; }
// Put records into bins, working from left to right
for (j=0; j<A.length; j++) {
B[count[(A[j]/rtok)%r]] = A[j];
count[(A[j]/rtok)%r] = count[(A[j]/rtok)%r] + 1;
}
for (j=0; j<A.length; j++) { A[j] = B[j]; } // Copy B back
}
}
static void radixsort(int A[], int k, int r, int n) {
int B[n];
int count[r];
int i, j, rtok;
for (i = 0, rtok = 1; i < k; i++, rtok *= r) { // For k digits
for (j = 0; j < r; j++) count[j] = 0; // Initialize count
// Count the number of records for each bin on this pass
for (j = 0; j < n; j++) count[(A[j]/rtok)%r]++;
// count[j] will be index in B for last slot of bin j.
// First, reduce count[0] because indexing starts at 0, not 1
count[0] = count[0] - 1;
for (j = 1; j < r; j++) count[j] = count[j-1] + count[j];
// Put records into bins, working from bottom of bin
// Since bins fill from bottom, j counts downwards
for (j = n-1; j >= 0; j--) {
B[count[(A[j]/rtok)%r]] = A[j];
count[(A[j]/rtok)%r] = count[(A[j]/rtok)%r] - 1;
}
for (j = 0; j < n; j++) A[j] = B[j]; // Copy B back
}
}
第一个内层 for 循环初始化数组 count 。第二个循环统计要分配到每个箱的记录数。第三个循环把 count 中的值从计数改为数组 B 中的下标。第四个循环从右到左把记录分配到各箱（数组 B 内）。最后一个循环只是把记录复制回数组 A ，为下一趟做好准备。变量 rtoi 存储 \(r^i\) ，用于第 \(i\) 次迭代中的装箱计算。
12.14.2.1. 基数排序分析¶
把 \(k\) 视为常数真的是一个合理的假设吗 ？或者说， \(k\) 与 \(n\) 之间是否存在某种关系？如果键范围有限，而且重复的键值很常见，那么 \(k\) 与 \(n\) 之间可能没有关系。为了更清楚地说明这种区别，用 \(N\) 表示 \(n\) 条记录所使用的不同键值的数目。于是 \(N \leq n\) 。因为表示 \(N\) 个不同的键值至少需要 \(\log_r N\) 个基数为 \(r\) 的数字位，所以我们知道 \(k \geq \log_r N\) 。
现在，考虑没有键重复的情形。如果有 \(n\) 个唯一的键，那么 \(n = N\) 。表示它们需要 \(n\) 个不同的值。因此现在表示这 \(n\) 个不同的键值至少需要 \(\log_r n\) 个基数为 \(r\) 的数字位。这意味着 \(k \geq \log_r n\) 。因为要区分这 \(n\) 个不同的键 至少 需要 \(\log n\) 个数字位（在一个常数因子内—也就是说，数字位的数目为 \(\Omega(\log n)\) ），所以 \(k\) 属于 \(\Omega(\log n)\) 。 这意味着基数排序需要 \(\Omega(n \log n)\) 时间来处理 \(n\) 个不同的键值 。
当然，键范围可能要大得多—— \(\log_r n\) 位只是 \(n\) 个不同值可能达到的最好情况。因此，对 \(k\) 的 \(\log_r n\) 估算可能过于乐观。这项分析的结论是：对于 \(n\) 个不同键值的一般情形，基数排序最好也只是 \(\Omega(n \log n)\) 的排序算法。
如果我们让基数 \(r\) 尽可能大，基数排序的运行时间可以（按常数因子）大幅改善。如果考虑整数键值，这最简单。取 \(r = 2^i\) ，其中 \(i\) 为某个值。换句话说， \(r\) 的取值与每一趟处理的键位数有关。位数每翻倍一次，趟数就减半。处理整数键值时，令 \(r = 256\) 可以让键一次处理一个字节。处理一个 32 位整数键只需四趟。在大多数计算机上，使用 \(r = 2^{16} = 64\mbox{K}\) 并非不合理，这样 32 位键只需两趟。当然，这需要一个大小为 64K 的 count 数组。只有当记录数约为 64K 或更多时，性能才会好。换句话说，要让基数排序高效，记录数必须相对于键规模足够大。在许多排序应用中，可以通过这种方式调整基数排序以获得更好的性能。
基数排序依赖于根据数字位做出固定数目多路选择的能力，以及对各箱的随机 访问。 因此，对于某些键类型，基数排序可能难以实现。 例如，如果键是实数或任意长度的字符串，那么在实现时就需要格外小心。 具体来说，基数排序需要谨慎判断何时已找到用于区分实数的"最后一位数字"， 或变长字符串中的最后一个字符。 在这些情形下，用 字母树 数据结构来实现基数排序的概念最为合适。
