14. 基数排序¶
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\) 次。
下面是一个把键放入桶中的练习。
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\) 次迭代中的装桶计算。
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 或更多时，性能才会好。
换句话说，要让基数排序高效，记录数必须相对于键规模足够大。
在许多排序应用中，可以通过这种方式调整基数排序以获得更好的性能。
基数排序依赖于根据数字位做出固定数目多路选择的能力，以及对各桶的随机 访问。 因此，对于某些键类型，基数排序可能难以实现。 例如，如果键是实数或任意长度的字符串，那么在实现时就需要格外小心。 具体来说，基数排序需要谨慎判断何时已找到用于区分实数的"最后一位数字"， 或变长字符串中的最后一个字符。 在这些情形下，用 字母树 数据结构来实现基数排序的概念最为合适。
