算法导论8 Problems 答案

8-1

a

由于数组\(A\)将会有\(n!\)个不同的输入，这些输入都会以等概率的形式出现，而且这些原始输入都是决策树\(T_A\)的叶节点。因此\(T_A\)中每个叶节点都有\(\dfrac{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{aligned} d(k)&=\min _{T \text{ have } k \text{ leaves}} \{D(T)\}\\ &=\min_{T \text{ have } k \text{ leaves}} \{D(T_{L}) + D(T_{R}) + k\}\\ &=\min_{i=1}^{k-1} \{\min_{LT \text{ have } i \text{ leaves}} \{D(LT)\} + \min_{T \text{ have } k-i \text{ leaves}} \{D(RT)\} +k\}\\ &=\min_{i=1}^{k-1} \{d(i)+d(k-i) +k\}\\ \end{aligned}\)

d

令\(f(i)=i\lg i+(k-i)\lg(k-i)\)，那么\(f'(i)=\lg i-\lg(k-i),f''(i)=\dfrac{1}{i\cdot \ln 2}+\dfrac{1}{(k-i)\cdot \ln 2}\)。

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

假设\(d(k_0)\ge ck_0\lg k_0\)，对于\(k_0< k\)都成立，那么有

\(\begin{aligned} d(k)&=\min_{i=1}^{k-1} \{d(i)+d(k-i) +k\}\\ &\ge \min_{i=1}^{k-1} \{ci\lg i+c(n-i)\lg (n-i) +k\}\\ &= c\cdot \min_{i=1}^{k-1} \{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&\qquad(A) \end{aligned}\)

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

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

e

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

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

f

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

8-2

a

直接使用计数排序，其中参数\(k=1\)，时间复杂度为\(\Theta(n+1)=\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

直接使用插入排序，不过算法的时间复杂度为\(\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，那么时间复杂度将会达到\(\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\left(\sum_{i=1}^n i\cdot c_i\right)=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

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

b

将红色水壶先随机摆放成一个排列\(r\)，那么此时的问题就变成了确定一个排列\(b\)，使得\(\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\)，即\(\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=\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=\Theta(n^2)}\)次。

8-5

a

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

b

其中一个为\(\langle6, 1, 7, 2, 8, 3, 9, 4, 10, 5\rangle\)。

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\)块，每块的长度为\(\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\)个数组为\(\langle A[j],A[j+k],A[j+2k],\dots\rangle\)，这些数组的长度总和为\(n\)。接下来，使用题目6.5-11对\(k\)个有序数组进行\(k\)路归并的算法（基于堆排序实现），即可以以\(O(n\lg k)\)的时间复杂度对\(k-\)排序算法进行排序。

f

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

8-6

a

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

b

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

\(\begin{aligned} \dbinom{2n}{n}&=\dfrac{\sqrt{4\pi n}\cdot\left(\dfrac{2n}{e}\right)^{2n}\cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)}{\left(\sqrt{2\pi n}\cdot\left(\dfrac{n}{e}\right)^{n}\cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)\right)^2}\\ &=\dfrac{2\sqrt{\pi n}\cdot\left(2n\right)^{2n}\cdot\dfrac{1}{e^{2n}}}{2\pi n\cdot n^{2n}\cdot \dfrac{1}{e^{2n}}} \cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)\\ &=\dfrac{2^{2n}}{\sqrt{\pi n}}\cdot \left(1+\Theta\left(\dfrac{1}{n}\right)\right)\\ &=\dfrac{2^{2n}}{\sqrt{\pi n}}\cdot \left(1+O\left(\dfrac{1}{n}\right)\right) \end{aligned}\)

那么可以得到\(h\ge 2n - \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=\langle1,3,\dots,2n-3,2n-1\rangle,B=\langle2,4,\dots,2n-2,2n\rangle\)时，按照题目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'\)位于比真正位置的\(q'\)靠后，即\(p'>q'\)。

更进一步的说明：算法\(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'\)上，在\(p'\)上，那么类似的，对\(B\)运行算法\(X\)后，有\(B[p']=0,B[q']=1\)；由于\(p'>q'\)，因此算法\(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'\)仍然可以视为是一系列COMPARE-EXCHANGE指令的集合，因此它可以视为一个不经意比较-交换排序算法。

d

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

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

因此，最终结论是至少\(\displaystyle{\sum_{j=1}^s\left\lfloor\dfrac{c_j}{s}\right\rfloor}\)行的全\(0\)干净行，至多\(s\)行的脏行，以及至少\(\displaystyle{r-\sum_{j=1}^s\left\lfloor\dfrac{c_j}{s}\right\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'\)行，使得\(s\mid r'\)即可。填充的内容是\((r'-r)\times s\)的\(+\infty\)。填充后的矩阵是\(r'\times s\)的大小，并且满足\(r'\ge r\ge 2s^2\)。因此将上面的算法作为子程序进行排序。步骤8完成后，将最后的\((r'-r)s\)个\(+\infty\)舍弃。

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