算法导论 — 8.3 基数排序算法导论

笔记
基数排序的做法为：对一组输入整数，先按最低位数字排好序，然后按次低位数字排好序，如此迭代，直至最后一步按最高位数字排好序，此时所有输入数据已排好序。基数排序要求对单个数字采用的排序算法是稳定的。
以十进制数为例，基数排序算法先按个位数字排序，然后按十位数字排序……直至最后按最高位数字排序。下图给出了一个例子。

文章图片

下面给出基数排序的伪代码。在下面的代码中，我们假设输入数组 A A A包含 n n n个 d d d位数，其中第 1 1 1位是最低位，第 d d d位是最高位。

文章图片

关于基数排序算法，有两点需要说明。
(1) 直观上，我们可能觉得应该先排序最高位数字，最后排序最低位数字。但是这样做，会产生额外的开销。我们仍然看上面的例子，先按百位数字排序，得到如下序列。

文章图片

在上面的序列中，按百位数字的不同分成了 5 5 5个子序列，分别标以不同的颜色。接下来我们要按十位数字排序。在这一步，我们并不是对整个序列进行排序，而是对 5 5 5个子序列分别进行排序，这需要额外的空间来记录 5 5 5个子序列的下标。
而基数排序算法先排序最低位数字，最后排序最高位数字。每一轮排序都是对整个数组进行排序，不会产生额外的空间开销。
(2) 基数排序要求每一轮排序都是稳定的。我们还是以上面的例子来说明这一点。第一轮排序完成后，得到的序列为 < 720 , 355 , 436 , 457 , 657 , 329 , 839 > <720, 355, {\color{red} 436}, 457, 657, 329, {\color{red} 839}> <720,355,436,457,657,329,839>。观察标红色的两个数 436 436 436和 839 839 839。由于第一轮按个位数字排序，故第一轮排序结束后， 436 436 436排在 839 839 839前面。第二轮按十位数字排序。 436 436 436和 839 839 839的十位数字都为 3 3 3，如果采用非稳定排序，那么第二轮排序结束后有可能 839 839 839排在 436 436 436之前，这显然不是我们想要的结果。故每一轮排序都必须是稳定的。
下面我们讨论基数排序的时间复杂度。给定 n n n个 d d d位数，其中每一位数有 k k k个可能的取值 ( 0 (0 (0 ~k ? 1 ) k?1) k?1)。如果基数排序每一轮都采用计数排序，那么每一轮消耗的时间为 Θ ( n + k ) Θ(n+k) Θ(n+k)。于是整个基数排序的运行时间为 Θ ( d ( n + k ) ) Θ(d(n+k)) Θ(d(n+k))。
计算机处理的都是二进制数。我们可以把基数排序的输入数据都看成二进制数，再做分析。给定 n n n个 b b b位二进制数和任何正整数 r ≤ b r ≤ b r≤b。如果基数排序每一轮都使用计数排序，那么基数排序可以在 Θ ( ( b / r ) ( n + 2 r ) ) Θ((b/r)(n+2^r)) Θ((b/r)(n+2r))时间内完成。这一结论不难证明。可以将一个 b b b位数二进制数看成是由 d = ? b / r ? d=?b/r? d=?b/r?个 r r r位数组成。于是总共要跑 ? b / r ? ?b/r? ?b/r?轮计数排序，每轮计数排序只对相应的 r r r位数进行。由于 r r r位数的取值范围为 0 0 0 ~2 r ? 1 2^r?1 2r?1，故每轮计数排序所花费的时间为 Θ ( n + 2 r ) Θ(n+2^r) Θ(n+2r)。于是得到，整个基数排序的运行时间为 Θ ( ( b / r ) ( n + 2 r ) ) Θ((b/r)(n+2^r)) Θ((b/r)(n+2r))。
对于给定的 n n n和 b b b，该如何选择 r r r，才能够最小化表达式 ( b / r ) ( n + 2 r ) (b/r)(n+2^r) (b/r)(n+2r)。下面分两点说明。

如果 b < ? l g n ? b < ?{\rm lg}n? b
如果 b ≥ ? l g n ? b ≥ ?{\rm lg}n? b≥?lgn?，即 n n n比较小， n n n不超过 2 b 2^b 2b，那么选择 r = ? l g n ? r = ?{\rm lg}n? r=?lgn?可以得到偏差不超过常系数范围内的最优时间代价。选择 r = ? l g n ? r = ?{\rm lg}n? r=?lgn?，得到的运行时间为 Θ ( ( b n / l g n ) Θ((bn/{\rm lg}n) Θ((bn/lgn)。如果 r r r值超过 ? l g n ? ?{\rm lg}n? ?lgn?，并且 r r r值逐步增加，表达式 ( b / r ) ( n + 2 r ) (b/r)(n+2^r) (b/r)(n+2r)分子中的 2 r 2^r 2r项比分母中的 r r r项增加要快，此时运行时间将超过 Θ ( ( b n / l g n ) Θ((bn/{\rm lg}n) Θ((bn/lgn)。反之，如果 r r r值小于 ? l g n ? ?{\rm lg}n? ?lgn?，并且 r r r值一直减小，表达式 ( b / r ) ( n + 2 r ) (b/r)(n+2^r) (b/r)(n+2r)中的 ( b / r ) (b/r) (b/r)项会增大，而 ( n + 2 r ) (n+2^r) (n+2r)保持为 Θ ( n ) Θ(n) Θ(n)，此时运行时间也将超过 Θ ( ( b n / l g n ) Θ((bn/{\rm lg}n) Θ((bn/lgn)。

练习
【算法导论 — 8.3 基数排序】8.3-1 参照图8-3的方法，说明RADIX-SORT在下列英文单词上的操作过程：COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX。
解

文章图片

8.3-2 下面的排序算法中哪些是稳定的：插入排序、归并排序、堆排序和快速排序？给出一个能使任何排序算法都稳定的方法。你所给出的方法带来的额外时间和空间开销是多少？
解
插入排序和归并排序是稳定的。堆排序和快速排序是不稳定的。
一个能使任何排序算法都稳定的方法是：对于一个输入数组 A [ 1.. n ] A[1..n] A[1..n]，新开一个数组 I D [ 1.. n ] ID[1..n] ID[1..n]，记录每个输入元素的下标；如果比较两个输入元素相等，再比较二者的下标，以确定二者的次序；如果排序过程中交换两个输入元素 A [ i ] A[i] A[i]和 A [ j ] A[j] A[j]，二者对应的下标 I D [ i ] ID[i] ID[i]和 I D [ j ] ID[j] ID[j]也同样做交换。
该方法引入了一个新数组 I D [ 1.. n ] ID[1..n] ID[1..n]，因此额外空间开销为 Θ ( n ) Θ(n) Θ(n)。该方法带来的额外时间开销取决于新数组 I D [ 1.. n ] ID[1..n] ID[1..n]中元素的比较次数，这一比较次数最多不会超过输入数组 A [ 1.. n ] A[1..n] A[1..n]中元素的比较次数，因此这一做法只会在原排序算法的运行时间上增加常数因子，而并不改变原排序算法的渐近运行时间。
8.3-3 利用归纳法来证明基数排序是正确的。在你所给出的证明中，在哪里需要假设所用的底层排序算法是稳定的？
略
8.3-4 说明如何在 O ( n ) O(n) O(n)时间内，对 0 0 0到 n 3 ? 1 n^3?1 n3?1区间内的 n n n个整数进行排序。
解
定义一种 n n n进制 3 3 3位数 x y z xyz xyz。由于所定义的 3 3 3位数为 n n n进制，因此每位数可能取值为 0 0 0 ~n ? 1 n-1 n?1，其数值为 ( x n 2 + y n + z ) (xn^2 + yn + z) (xn2+yn+z)。显然，这样的 3 3 3位数最小值为 0 0 0，最大值为 ( n ? 1 ) n 2 + ( n ? 1 ) n + ( n ? 1 ) = n 3 ? 1 (n?1)n^2 + (n?1)n + (n?1) = n^3?1 (n?1)n2+(n?1)n+(n?1)=n3?1，所以其取值范围为 0 0 0 ~n 3 ? 1 n^3?1 n3?1。
对这样定义的 3 3 3位数进行基数排序，位数 d = 3 d = 3 d=3，每一位数有 k = n k = n k=n个可能的取值。排序的时间复杂度为 Θ ( d ( n + k ) ) = Θ ( 3 ( n + n ) ) = Θ ( n ) Θ(d(n+k)) = Θ(3(n+n)) = Θ(n) Θ(d(n+k))=Θ(3(n+n))=Θ(n)。
8.3-5 在本节给出的第一个卡片排序算法中，为排序 d d d位十进制数，在最坏情况下需要多少轮排序？在最坏情况下，操作员需要记录多少堆卡片？
略
代码链接：https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter08/Section_8.3/RadixSort