算法导论 8 Problems 答案

8-1

a

由于数组 $A$ 将会有 $n!$ 个不同的输入，这些输入都会以等概率的形式出现，而且这些原始输入都是决策树 $T_A$ 的叶节点。因此 $T_A$ 中每个叶节点都有 ${\displaystyle \frac{1}{n!}}$ 的概率被原始输入命中，而其它内部节点由于不是来自原始输入，因此它们不会被原始输入命中，概率值为 $0$。

b

当一棵树 $LT$ 和另外一颗树 $RT$ 与一个祖先节点共同构成一棵树 $T$ 后，$LT,RT$ 中所有节点的深度都增加了 $1$（当然也包括了叶节点）。由于祖先节点必定不是 $T$ 的叶节点，因此 $T$ 的叶节点必定来自于 $LT,RT$ 中的叶节点，并且两棵子树的叶节点总数为 $k$。由于所有非祖先节点都增加了 $1$，那么按照 $D$ 的定义，在 $D(LT),D(RT)$ 的基础上，$D(T)$ 中所有的叶节点的深度都要增加 $1$。因此 $D(T)=D(LT)+D(RT)+k$。

c

如果树 $T$ 的叶子节点的总数为 $k$，那么必有 $i$ 个节点来自左子树 $T_L$，$k-i$ 个节点来自右子树 $T_R$。如果 $D(T)$ 需要最小化，那么各自独立的 $D(T_L),D(T_R)$ 也需要最小化，根据 $d,D$ 的定义，有：

$\begin{array}{rl}d(k)& =\underset{T\text{ have }k\text{ leaves}}{min}\{D(T)\}\\ & =\underset{T\text{ have }k\text{ leaves}}{min}\{D(T_L)+D(T_R)+k\}\\ & =\underset{i=1}{\overset{k-1}{min}}\{\underset{LT\text{ have }i\text{ leaves}}{min}\{D(LT)\}+\underset{T\text{ have }k-i\text{ leaves}}{min}\{D(RT)\}+k\}\\ & =\underset{i=1}{\overset{k-1}{min}}\{d(i)+d(k-i)+k\}\end{array}$

d

令 $f(i)=i\lg i+(k-i)\lg (k-i)$，那么 $f^{\prime }(i)=\lg i-\lg (k-i),f^{″}(i)={\displaystyle \frac{1}{i\cdot \ln 2}}+{\displaystyle \frac{1}{(k-i)\cdot \ln 2}}$。

当 $f^{\prime }(i)=0$ 时，得到 $i={\displaystyle \frac{k}{2}}$，此时得到 $f^{″}\left({\displaystyle \frac{k}{2}}\right)={\displaystyle \frac{1}{k\cdot \ln 2}}>0$，也就是说 $f(i)$ 在 $i={\displaystyle \frac{k}{2}}$ 处取到最小值 $f\left({\displaystyle \frac{k}{2}}\right)=k\lg k-k$。

假设 $d(k_0)\ge c{k}_0\lg k_0$，对于 $k_0<k$ 都成立，那么有

$\begin{array}{rl}d(k)& =\underset{i=1}{\overset{k-1}{min}}\{d(i)+d(k-i)+k\}\\ & \ge \underset{i=1}{\overset{k-1}{min}}\{ci\lg i+c(n-i)\lg (n-i)+k\}\\ & =c\cdot \underset{i=1}{\overset{k-1}{min}}\{i\lg i+(n-i)\lg (n-i)\}+k\\ & =c(k\lg k-k)+k\\ & =ck\lg k+(1-c)k\\ & \ge ck\lg k& (A)\end{array}$

其中，步骤 $(A)$ 假设了 $c\le 1$。

那么最终令 $c=min\{1,d(2)/2\}$。由数学归纳法，$d(k)=\mathrm{\Omega }(k\lg k)$ 成立。

e

由于决策树 $T_A$ 一共有 $n!$ 个叶节点，因此 $D(T_A)\ge d(n!)=\mathrm{\Omega }(n!\lg (n!))$，即 $D(T_A)=\mathrm{\Omega }(n!\lg (n!))$.

那么平均时间复杂度满足 $T(n)$ 满足 $T(n)={\displaystyle \frac{D(T_A)}{n!}}=\mathrm{\Omega }(\lg (n!))=\mathrm{\Omega }(n\lg n)$。

f

以上证明说明了确定性算法 $A$ 中，每一个决策都是最优的。如果算法 $B$ 采用随机决策，那么算法 $B$ 可能会选到不是最优的决策，从而导致算法 $B$ 的平均时间复杂度比 $A$ 高。在这时，原本的算法 $A$ 就比算法 $B$ 优秀。

8-2

a

直接使用计数排序，其中参数 $k=1$，时间复杂度为 $\mathrm{\Theta }(n+1)=\mathrm{\Theta }(n)$。

b

直接使用快速排序，严格来说只需要调用一次算法 PARTITION 就可以完成。

SORT-0-1(A, n)
  for i = 1 to n
    if A[i] == 0
      exchange A[i] and A[n]
      PARTITION(A, 1, n)
      break
  

c

直接使用插入排序，不过算法的时间复杂度为 $\mathrm{\Theta }(n^2)$。

d

可以使用算法 (a) 解决，因为它同时满足了稳定性和时间复杂度的要求，直接以键的形式调用即可。

算法 (b) 不能的原因是不保证稳定性，算法 (c) 不能的原因是时间复杂度不满足要求。

e

如下算法做到了原地交换排序，并且是 $O(n+k)$ 的时间复杂度，但是不是稳定的，第 13 行的 while 循环每执行一次那么总会有一个数到达了正确的位置。

COUNT-SORT'''(A, n, k)
  let B[0 : k], C[0 : k] and D[0 : k] be new arrays
  for i = 0 to k
    C[i] = 0
  for j = 1 to n
    C[A[j]] = C[A[j]] + 1
  // C[i] now contains the number of elements equal to i.
  for i = 1 to k
    C[i] = C[i] + C[i – 1]
    B[i] = C[i - 1] + 1
    D[i] = C[i]
  // C [i] now contains the number of elements less than or equal to i.
  // B是每一段的起点，C是每一段的终点，当B[i] > C[i]说明这一段所有数已经复位。
  for i = 1 to n
    while B[A[i]] <= C[A[i]] and (i <= C[A[i]] or i > D[A[i]])
      k = A[i]
      exchange A[i] and A[C[k]]
      C[k] = C[k] - 1

8-3

a

先将每个数中按照数位个数放入每个桶中，然后每个桶内部使用基数排序即可（注意这里的基数排序算法 RADIX-SORT' 相比普通的基数排序算法 RADIX-SORT，多了一个判断数组 $A$ 是否为空的操作，如果为空那么立即返回。如果盲目运行 RADIX-SORT，那么时间复杂度将会达到 $\mathrm{\Theta }(n^2)$）。

// m是数组长度。假设每个数x都有属性digits表示位数个数。
BUCKET-SORT`(A, m, n)
  let B[1 : n] be a new array
  for i = 1 to n
    make B[i] an empty list
  for i = 1 to m
    insert A[i] into list B[A[i].digits]
  for i = 1 to n
    RADIX-SORT'(B[i], B[i].size, i)
  concatenate the lists B[1], B[2], ... , B[n] together in order
  return the concatenated lists

最终，算法的时间复杂度为 ${\displaystyle O(\sum _{i=1}^{n}i\cdot c_i)=O(n)}$，其中 $c_i$ 表示数位为 $i$ 的数的个数。

b

本算法使用的是自顶向下的桶排序算法，先考虑第一个字母，按照字母将它们分到不同的桶中，然后再递归处理每一个桶。将每个桶的字符串排好序后，再将这些字符串数组拼接在一起，从而保证了字典序。

由于每个字符串的每个字符都只会被访问一次，因此排序的时间复杂度为 $O(n)$。

BUCKET-SORT`(S, pos)
  if S.size == 0
    return
  let B['a' : 'z'] be a new array
  let B0 be a new empty list
  for i = 'a' to 'z'
    make B[i] an empty list
  for i = 1 to S.size
    if pos <= S[i].size
      insert S[i] into list B[S[i, pos]]
    else
      insert S[i] into list B0
  for i = 'a' to 'z'
    BUCKET-SORT'(B[i], pos + 1)
  concatenate the lists B0, B['a'], B['b'], ... , B['z'] together in order
  return the concatenated lists

8-4

a

对于每一个红色水瓶，遍历每个蓝色水瓶进行倒水实验。如果发现一样多，那么相当于是匹配的，将这两个瓶子挪开并放到一边，拿下一个红色水瓶进行同样的尝试；如果尝试到只剩下一个，那么就不用尝试了。这个算法需要的次数最坏达到 ${\displaystyle (\genfrac{}{}{0ex}{}{n}{2})}={\displaystyle \frac{n(n-1)}{2}}=\mathrm{\Theta }(n^2)$ 次。

b

将红色水壶先随机摆放成一个排列 $r$，那么此时的问题就变成了确定一个排列 $b$，使得 $\mathrm{\forall }1\le i\le n,r_i=b_i$ 都成立。潜在的序列 $b$ 的输入一共有 $n!$ 个。而每一次比较，都会产生小于、等于和大于三种结果。因此假设这棵决策树是一个三叉树，其叶节点表示原始输入，内部节点表示比较的决策过程，那么其高度 $h$ 满足 $3^h\ge l\ge n!$，因此 $h\ge n{\log }_{3}n$。因此对于原始输入中的叶节点而言，比较次数的期望至少为 $n{\log }_{3}n$，即 $\mathrm{\Omega }(n\lg n)$。

c

这个匹配算法如下进行：在 $n$ 个蓝色水壶中随机选择一个出来，假设为 $b_i$，然后将每个红色水壶逐个和 $b_i$ 比较，并且按照比较结果分别归类到小于，等于，大于三部分。其中等于的那一部分恰好仅有一个，与 $b_i$ 匹配，假设其为 $r_i$。那么此时划分出了小于部分 $r_{1:i-1}$，大于部分 $r_{i+1:n}$。那么接下来使用 $r_i$ 同样对剩下的 $n-1$ 个蓝色水壶进行比较和划分，假设小于部分为 $b_{1:i-1}$，大于部分为 $b_{i+1:n}$。那么当前步骤总共花费了 $2n-1=\mathrm{\Theta }(n)$ 次比较。接下来分别对 $(r_{1:i-1},b_{1:i-1}),(r_{i+1:n},b_{i+1:n})$ 进行递归操作即可。

由于这个比较过程的行为和算法 RANDOMIZED-QUICKSORT 完全一致，因此期望比较次数为 $O(n\lg n)$。

当每次选到的蓝色水壶都是当前堆中最大或者是最小的一个，那么比较次数将达到最大，为 ${\displaystyle \sum _{i=1}^n(2i-1)=n^2=\mathrm{\Theta }(n^2)}$ 次。

8-5

a

此时式子可以转化为 $A[i]\le A[i+1]$，即有序。

b

其中一个为 $⟨6,1,7,2,8,3,9,4,10,5⟩$。

c

整个不等式两边同乘 $k$，得到 ${\displaystyle \sum _{j=i}^{i+k-1}A[j]\le \sum _{j=i+1}^{i+k}A[j]}$。消去中间项 $A[i+1],A[i+2],\dots ,A[i+k-1]$，最终得到 $A[i]\le A[i+k]$。

d

这个算法将使用改进的快速排序算法 QUICKSORT 作为子程序进行排序，其平均、最坏时间复杂度为 $O(n\lg n)$。

K-SORTED(A, n, k)
  for i = 1 to k
    let B be new array
    for j = i to n by k
      INSERT(B, A[j])
    QUICKSORT(B, B.size)
    p = 0
    for j = i to n by k
      p = p + 1
      A[j] = B[p]

算法 K-SORTED 将数组 $A$ 均匀地划分了 $k$ 块，每块的长度为 $\mathrm{\Theta }(n/k)$。那么对每一段数组使用算法 QUICKSORT 进行排序，其时间复杂度为 $O(n/k\lg (n/k))$。将这 $k$ 段进行综合，那么最终时间复杂度为 $k\cdot O(n/k\lg (n/k))=O(n\lg (n/k))$。

e

我们可以将数组 $A$ 均匀地拆分成 $k$ 个有序的，其中第 $j$ 个数组为 $⟨A[j],A[j+k],A[j+2k],\dots ⟩$，这些数组的长度总和为 $n$。接下来，使用题目 6.5-11 对 $k$ 个有序数组进行 $k$ 路归并的算法（基于堆排序实现），即可以以 $O(n\lg k)$ 的时间复杂度对 $k-$ 排序算法进行排序。

f

算法 K-SORTED 将数组 $A$ 均匀地划分了 $k$ 块，每块的长度为 $\mathrm{\Theta }(n/k)$。那么对每一段数组使用算法 QUICKSORT 进行排序，其时间复杂度同样有下界 $\mathrm{\Omega }(n/k\lg (n/k))$。将这 $k$ 段进行综合，那么最终整个算法 K-SORTED 有下界 $k\cdot \mathrm{\Omega }(n/k\lg (n/k))=\mathrm{\Omega }(n\lg (n/k))$。舍弃常数 $k$ 后，即为 $\mathrm{\Omega }(n\lg n)$。

8-6

a

如果两个数组长度为 $n$ 的数组是有序的（即对于数组 $⟨1,2⟩$，划分 $⟨[1],[2]⟩$ 和 $⟨[2],[1]⟩$ 视为不同的划分），那么一共有 ${\displaystyle (\genfrac{}{}{0ex}{}{2n}{n})}$ 种划分方式。

b

至少 ${\displaystyle (\genfrac{}{}{0ex}{}{2n}{n})}$ 个叶节点的树的高度 $h$ 满足 $2^h\ge l\ge {\displaystyle (\genfrac{}{}{0ex}{}{2n}{n})}$，可以得到 $h\ge \lg {\displaystyle (\genfrac{}{}{0ex}{}{2n}{n})}$。根据斯特林公式，可以将值 ${\displaystyle (\genfrac{}{}{0ex}{}{2n}{n})}$ 如下进行近似：

$\begin{array}{rl}{\displaystyle (\genfrac{}{}{0ex}{}{2n}{n})}& ={\displaystyle \frac{\sqrt{4\pi n}\cdot {\left({\displaystyle \frac{2n}{e}}\right)}^{2n}\cdot (1+\mathrm{\Theta }\left({\displaystyle \frac{1}{n}}\right))}{{(\sqrt{2\pi n}\cdot {\left({\displaystyle \frac{n}{e}}\right)}^n\cdot (1+\mathrm{\Theta }\left({\displaystyle \frac{1}{n}}\right)))}^2}}\\ & ={\displaystyle \frac{2\sqrt{\pi n}\cdot {\left(2n\right)}^{2n}\cdot {\displaystyle \frac{1}{e^{2n}}}}{2\pi n\cdot n^{2n}\cdot {\displaystyle \frac{1}{e^{2n}}}}}\cdot (1+\mathrm{\Theta }\left({\displaystyle \frac{1}{n}}\right))\\ & ={\displaystyle \frac{2^{2n}}{\sqrt{\pi n}}}\cdot (1+\mathrm{\Theta }\left({\displaystyle \frac{1}{n}}\right))\\ & ={\displaystyle \frac{2^{2n}}{\sqrt{\pi n}}}\cdot (1+O\left({\displaystyle \frac{1}{n}}\right))\end{array}$

那么可以得到 $h\ge 2n-\mathrm{\Theta }(\sqrt{n})$，即 $h\ge 2n-o(n)$。由于这个决策树的高度至少为 $2n-o(n)$，因此比较次数至少为 $2n-o(n)$。

c

不失一般性，假设 $A[i],B[j]$ 是原本在序列 $A,B$ 中的两个元素，并且合并后，$B[j]$ 紧接在 $A[i]$ 的后面。那么在合并过程中，如果不对 $A[i]$ 和 $B[j]$ 进行比较，那么将无法确定 $A[i]$ 和 $B[j]$ 在合并的序列后哪一个数在前面，哪一个数在后面，那么忽略掉这两个数，哪怕是之后的所有数 $A[i+1:],B[j+1:]$ 相互都进行比较了，仍然无法确定出一个有序的序列。因此 $A[i]$ 和 $B[j]$ 必须相互进行比较。

d

每一次迭代，两个序列中的其中一个数将会被安排位置。由于一共有 $2n$ 个数，因此至少需要进行 $2n-1$ 次比较，才能够确定出整个有序序列。当 $A=⟨1,3,\dots ,2n-3,2n-1⟩,B=⟨2,4,\dots ,2n-2,2n⟩$ 时，按照题目 8-6-c 的结论，比较次数将会达到 $2n-1$ 的最大值。

8-7

a

由于 $A[p]$ 是最小的无法排序到正确的位置的元素，那么说明小于 $A[p]$ 的所有元素都已经排序到了正确的位置。而 $A[q]$ 却占据了 $A[p]$ 原有的位置，此时 $A[q]$ 放置的位置也是不正确的，那么说明 $A[q]\ge A[p]$。如果 $A[q]=A[p]$，那么序列的有序性不会受到影响，这个位置也是 $A[q]$ 的正确位置。因此仅存在 $A[q]>A[p]$ 的可能性。

根据数组 $B$ 的定义，$A[p]\le A[p]$ 必定成立，所以 $B[p]=0$；由于 $A[q]>A[p]$，所以 $B[q]=1$。

b

运行算法 $X$ 后，如果 $A[p]$ 排序后没有到达正确的位置，那么说明 $A[p]$ 排序后的位置 $p^{\prime }$ 位于比真正位置的 $q^{\prime }$ 靠后，即 $p^{\prime }>q^{\prime }$。

更进一步的说明：算法 $X$ 是不经意比较 - 交换排序算法，算法 $X$ 内部是将子程序 COMPARE-EXCHANGE 作为一系列指令，直接对数组进行操作。也就是说，算法 $X$ 没有分支判断结构，循环结构也可以转化为顺序结构。舍去循环结构后，算法 $X$ 的伪代码将会是如下的样子：

X(A, n)
  COMPARE-EXCHANGE(A, ?, ?)
  COMPARE-EXCHANGE(A, ?, ?)
  COMPARE-EXCHANGE(A, ?, ?)
  COMPARE-EXCHANGE(A, ?, ?)
  ...

因此，本题的证明思路是，比较数组 $A$ 和由 $A$ 构造出来的数组 $B$ 在运行这个算法 $X$ 上的行为是一致的。

以下讨论三种情况：

1. $A[i],A[j]\le A[p]$，那么有 $B[i]=B[i]=0$。如果 $A[i]>A[j]$，那么调用 COMPARE-EXCHANGE(A, i, j) 时，$A[i]$ 和 $A[j]$ 将会被交换，此时 $B[i]=B[j]=0$；虽然调用 COMPARE-EXCHANGE(B, i, j) 不会真正交换，但是并不影响调用完成后保持 $B[i]\le B[j]=0$ 的性质，我们可以视为 $B[i]$ 与 $B[j]$ 发生了交换。如果 $A[i]\le A[j]$，那么无论调用 COMPARE-EXCHANGE(A, i, j) 还是 COMPARE-EXCHANGE(B, i, j)，$A[i]$ 与 $A[j]$ 以及 $B[i]$ 与 $B[j]$ 都不会发生交换。因此，当 $A[i],A[j]\le A[p]$ 时，算法 $X$ 中针对这一类满足 $A[i],A[j]\le A[p]$ 的指令 COMPARE-EXCHANGE(A, i, j) 和 COMPARE-EXCHANGE(B, i, j) 的行为是一致的。

2. 同样的，当 $A[i],A[j]>A[p]$，那么有 $B[i]=B[i]=1$。对这类满足 $A[i],A[j]>A[p]$ 的指令的分析和第 1 种情况完全相同，只是 $B[i]=B[j]=1$。故有结论：当 $A[i],A[j]>A[p]$ 时，算法 $X$ 中针对这一类满足 $A[i],A[j]>A[p]$ 的指令 COMPARE-EXCHANGE(A, i, j) 和 COMPARE-EXCHANGE(B, i, j) 的行为是一致的。

3. 当 $A[i]\le A[p],A[j]>A[p]$ 时，$B[i]=0,B[j]=1$，此时调用 COMPARE-EXCHANGE(A, i, j) 和 COMPARE-EXCHANGE(B, i, j) 时，都不会发生交换；当 $A[i]>A[p],A[j]\le A[p]$ 时，$B[i]=1,B[j]=0$，此时调用 COMPARE-EXCHANGE(A, i, j) 和 COMPARE-EXCHANGE(B, i, j) 时，都会发生交换。

因此，对于数组 $A$ 和数组 $B$，对于任意一条 COMPARE-EXCHANGE 指令，可以看作要么 $A[i]$ 和 $A[j]$ 与 $B[i]$ 和 $B[j]$ 都发生交换，要么 $A[i]$ 和 $A[j]$ 与 $B[i]$ 和 $B[j]$ 都不发生交换，行为是一致的。最终，由于 $A[p]$ 不在原来的位置 $q^{\prime }$ 上，在 $p^{\prime }$ 上，那么类似的，对 $B$ 运行算法 $X$ 后，有 $B[p^{\prime }]=0,B[q^{\prime }]=1$；由于 $p^{\prime }>q^{\prime }$，因此算法 $X$ 未能对数组 $B$ 完成排序。

c

因为奇数步骤才对数组 $A$ 的元素进行排序，此时使用的排序算法中将会对数组 $A$ 中的元素进行访问，并且进行交换。而偶数步骤中，仅仅是涉及了对数组 $A$ 本身形状的变换，并没有对数组元素进行操作。事实上，偶数步的操作仅仅是对数组元素的位置进行重新排列，因此在每个步骤，我们可以列出一个映射 $f$，表示每个旧位置到新位置的变换，然后在下一步奇数步骤上执行排序时，使用的排序指令是经过映射变换后的数组的下标。

例如，一开始输入的数据的下标如下：

1  2  3
4  5  6
7  8  9
10 11 12
13 14 15
16 17 18

那么在第 3 步中，执行的每行排序算法中将会包含指令：COMPARE-EXCHANGE(A, 1, 2), COMPARE-EXCHANGE(A, 1, 3), COMPARE-EXCHANGE(A, 2, 3)。

经过第 2 个步骤的变换后，对应数的下标位置如下：

1  7  13
2  8  14
3  9  15
4  10 16
5  11 17
6  12 18

那么在第 3 步中，执行的每行排序算法中将会包含指令：COMPARE-EXCHANGE(A, 1, 7), COMPARE-EXCHANGE(A, 1, 13), COMPARE-EXCHANGE(A, 7, 13)。

因此本质上这个列排序算法 $X^{\prime }$ 仍然可以视为是一系列 COMPARE-EXCHANGE 指令的集合，因此它可以视为一个不经意比较 - 交换排序算法。

d

在第一个步骤完成后，第 $j$ 列从上到下都是由一些 $0$ 紧跟着一些 $1$。如果第 $j$ 列上面有 $c_j$ 个 $0$，那么第 $j$ 列下面有 $r-c_j$ 个 $1$。由于每一列排完序后，$0$ 和 $1$ 相邻的坐标个数最多只有 $1$ 个，因此将每一列的 $r$ 个元素均匀划分成 $s$ 个区间后，前 $\lfloor {\displaystyle \frac{c_j}{s}}\rfloor$ 个区间全部为 $0$，后 ${\displaystyle \frac{r}{s}}-\lfloor {\displaystyle \frac{c_j}{s}}\rfloor -1$ 个区间全部区间全部为 $1$。那么第 2 个步骤完成后，整个矩阵至少有 ${\displaystyle \sum _{j=1}^s\lfloor {\displaystyle \frac{c_j}{s}}\rfloor }$ 个全 $0$ 行，至少 ${\displaystyle \sum _{j=1}^s\lfloor {\displaystyle \frac{r}{s}}-\lfloor {\displaystyle \frac{c_j}{s}}\rfloor -1\rfloor =r-\sum _{j=1}^s\lfloor {\displaystyle \frac{c_j}{s}}\rfloor -s}$ 个全 $1$ 行。

那么接下来每一列的排序可以进行如下变换：将 ${\displaystyle \sum _{j=1}^s\lfloor {\displaystyle \frac{c_j}{s}}\rfloor }$ 个全 $0$ 行向顶部转移并合并，形成 ${\displaystyle \sum _{j=1}^s\lfloor {\displaystyle \frac{c_j}{s}}\rfloor }$ 个全 $0$ 干净行；将 ${\displaystyle r-\sum _{j=1}^s\lfloor {\displaystyle \frac{c_j}{s}}\rfloor -s}$ 个全 $1$ 行。向底部转移并合并，形成 ${\displaystyle r-\sum _{j=1}^s\lfloor {\displaystyle \frac{c_j}{s}}\rfloor -s}$ 个全 $1$ 干净行。剩下的至多 $s$ 行都是脏行，直接对这个 $s\times s$ 的区域每一列进行列排序即可。可以发现这种操作和对整个列的 $r$ 个元素进行排序是相同的（因为之前对全 $0$ 行和全 $1$ 行的操作保证了顶部已经都是 $0$，底部都是 $1$。）

因此，最终结论是至少 ${\displaystyle \sum _{j=1}^s\lfloor {\displaystyle \frac{c_j}{s}}\rfloor }$ 行的全 $0$ 干净行，至多 $s$ 行的脏行，以及至少 ${\displaystyle r-\sum _{j=1}^s\lfloor {\displaystyle \frac{c_j}{s}}\rfloor -s}$ 行的全 $1$ 干净行。

e

按列优先的方式读取步骤 4 后得到的矩阵，相当于是按行优先读取步骤 3 后得到的矩阵。正如题目 8-7-d 的结论，中间有一个 $s\times s$ 的脏区域，因此按行优先的顺序读取步骤 3 得到的矩阵后，将会有一个长度至多为 $s^2$ 的脏区域序列，前面的是全 $0$ 干净区域，后面的是全 $1$ 干净区域的序列。

f

由于 $r\ge 2s^2$ 成立。因此，题目 8-7-e 中间的 $s^2$ 个脏区域序列最多处在 $2$ 个不同的列中。接下来分别考虑两种情况。

• 如果这个 $s^2$ 的脏区域序列横跨在两个不同的列中，那么其起点必定在前一列的下半部分，其终点必定在后一列的上半部分；步骤 5 对这两个列排完序后，前一列的起点会有所继续下降，后一列的终点会有所上升，但是起点在前一列的下半部分，其终点在后一列的上半部分这个事实仍然不变。第 6 行的操作则是将前一列的下半行接在后一列的上半行前面，形成一个新列，此时整个脏区域必定在同一列。步骤 7 则继续对每一列进行排序，这对其它干净列没有影响；对含有脏区域的一列，将会重新排序。步骤 7 完成后，只有这一列会产生一个 $0,1$ 相邻的坐标。步骤 8 将整个序列还原，按列优先读取并不会改变所有数的位置，此时将产生一个全排序的 0-1 输出。

• 如果这个 $s^2$ 的脏区域序列仅在同一列中，那么步骤 5 的排序完成后就可以停止了，只有这一列会产生一个 $0,1$ 相邻的坐标。步骤 6 和 7 的变换和排序不会产生任何改变，因为步骤 6 的操作完成了，每一列就已经是单调有序的，步骤 7 的列排序操作是无用的。步骤 8 则是将数组还原。最终产生一个全排序的 0-1 输出。

因此，这个不经意比较 - 交换排序算法可以对任何一个只含 0 和 1 的序列正确排序，那么根据 0-1 排序引理，这个算法可以对任意输入值的序列进行排序。

g

如果 $s\nmid r$，那么按照步骤 2 的变换，前一列的最后一个数（如果不是全 $0$，那么最后一个数必定是 $1$）将会和后一列的第一个数（如果不是全 $0$，那么第一个数必定是 $0$）有可能在某一行中是相邻的，这种接触最多有 $s-1$ 个（第 $1$ 列和第 $2$ 列的首尾相接，第 $2$ 列和第 $3$ 列的首尾相接…… 第 $s-1$ 列和第 $s$ 列首位相接）。再加上题目 8-7-d 的分析结果（每一列中，$0$ 和 $1$ 相邻的坐标个数最多只有 $1$ 个），故至多有 $2s-1$ 个行组成的脏区域。

因此步骤 4 完成后，中间会有一个最多 $(2s-1)s$ 个元素组成的脏区域。为了保证这些元素最多只占半列的位置，使得步骤 5-8 正确进行，$r$ 需要满足 $r\ge 2\cdot (2s-1)s$，即 $r\ge 4s^2-2s$。

h

将 $r$ 行的序列填充到 $r^{\prime }$ 行，使得 $s\mid r^{\prime }$ 即可。填充的内容是 $(r^{\prime }-r)\times s$ 的 $+\mathrm{\infty }$。填充后的矩阵是 $r^{\prime }\times s$ 的大小，并且满足 $r^{\prime }\ge r\ge 2s^2$。因此将上面的算法作为子程序进行排序。步骤 8 完成后，将最后的 $(r^{\prime }-r)s$ 个 $+\mathrm{\infty }$ 舍弃。

证明：基于原排序算法的正确性，最后 $(r^{\prime }-r)s$ 个元素必为 $+\mathrm{\infty }$，舍去这些 $+\mathrm{\infty }$ 后将得到原本正确的排序结果。因此这个新算法是正确的。