8.1 排序算法的下界

8.1-1

解：n-1。

8.1-2

解： Θ ( n lg ⁡ n ) \Theta(n\lg n) Θ(nlgn)。

8.1-3

证明：

n ! 2 ≤ 2 n \frac{n!}{2} \le 2^n 2n!​≤2n

n ! n ≤ 2 n \frac{n!}{n} \le 2^n nn!​≤2n

n ! 2 n ≤ 2 n ⇔ n ! ≤ 4 n \frac{n!}{2^n} \le 2^n \Leftrightarrow n! \le 4^n 2nn!​≤2n⇔n!≤4n

对后两种，只能对较小的n存在。

8.1-4

证明：

( k ! ) n / k ≤ 2 h (k!)^{n/k} \le 2^h (k!)n/k≤2h

h ≥ lg ⁡ ( k ! ) n / k = ( n / k ) lg ⁡ ( k ! ) ≥ ( n / k ) ( k / 2 ) lg ⁡ ( k / 2 ) (ex8.1.2) = 1 2 n lg ⁡ k − 1 2 n = Ω ( n lg ⁡ k ) \begin{aligned} h &\ge \lg(k!)^{n/k} \\ &= (n/k)\lg(k!) \\ &\ge (n/k)(k/2)\lg(k/2) & \text{(ex 8.1.2)}\\ &= \frac{1}{2}n\lg{k} - \frac{1}{2}n \\ &= \Omega(n\lg{k}) \end{aligned} h​≥lg(k!)n/k=(n/k)lg(k!)≥(n/k)(k/2)lg(k/2)=21​nlgk−21​n=Ω(nlgk)​(ex8.1.2)​

8.2 计数排序

8.2-1

解：中间过程略，最后B是{0, 0, 1, 1, 2, 2, 3, 3, 4, 6, 6}，C是{0, 2, 4, 6, 8, 8, 9}

8.2-2 8.2-3

证明（来自参考答案）：

Notice that the correctness argument in the text does not depend on the order in which A A A is processed. The algorithm is correct no matter what order is used!

But the modified algorithm is not stable. As before, in the final for loop an element equal to one taken from A A A earlier is placed before the earlier one (i.e., at a lower index position) in the output array B B B. The original algorithm was stable because an element taken from A A A later started out with a lower index than one taken earlier. But in the modified algorithm, an element taken from A A A later started out with a higher index than one taken earlier.

In particular, the algorithm still places the elements with value k k k in positions C [ k − 1 ] + 1 C[k - 1] + 1 C[k−1]+1 through C [ k ] C[k] C[k], but in the reverse order of their appearance in A A A.

8.2-4

解：

COUNTING-INTERVAL(A, a, b)let C[0..k] be a new arraycount = 0for i = 0 to kC[i] = 0for j = 1 to A.lengthC[A[j]] = C[A[j]] + 1for i = ceiling(a) to floor(b)count = count + C[i]return count

8.3 基数排序

8.3-1

解：

0 1 2 3 COW SE A T A B B AR DOG TE A B A R B IG SEA MO B E A R B OX RUG TA B T A R C OW ROW DO G S E A D IG MOB RU G T E A D OG BOX DI G D I G E AR TAB BI G B I G F OX BAR BA R M O B M OB EAR EA R D O G N OW TAR TA R C O W R OW DIG CO W R O W R UG BIG RO W N O W S EA TEA NO W B O X T AB NOW BO X F O X T AR FOX FO X R U G T EA \begin{array}{cccc} 0 & 1 & 2 & 3 \\ \hline \text{COW} & \text{SE$\textbf{A}$} & \text{T$\textbf{A}$B} & \text{$\textbf{B}$AR} \\ \text{DOG} & \text{TE$\textbf{A}$} & \text{B$\textbf{A}$R} & \text{$\textbf{B}$IG} \\ \text{SEA} & \text{MO$\textbf{B}$} & \text{E$\textbf{A}$R} & \text{$\textbf{B}$OX} \\ \text{RUG} & \text{TA$\textbf{B}$} & \text{T$\textbf{A}$R} & \text{$\textbf{C}$OW} \\ \text{ROW} & \text{DO$\textbf{G}$} & \text{S$\textbf{E}$A} & \text{$\textbf{D}$IG} \\ \text{MOB} & \text{RU$\textbf{G}$} & \text{T$\textbf{E}$A} & \text{$\textbf{D}$OG} \\ \text{BOX} & \text{DI$\textbf{G}$} & \text{D$\textbf{I}$G} & \text{$\textbf{E}$AR} \\ \text{TAB} & \text{BI$\textbf{G}$} & \text{B$\textbf{I}$G} & \text{$\textbf{F}$OX} \\ \text{BAR} & \text{BA$\textbf{R}$} & \text{M$\textbf{O}$B} & \text{$\textbf{M}$OB} \\ \text{EAR} & \text{EA$\textbf{R}$} & \text{D$\textbf{O}$G} & \text{$\textbf{N}$OW} \\ \text{TAR} & \text{TA$\textbf{R}$} & \text{C$\textbf{O}$W} & \text{$\textbf{R}$OW} \\ \text{DIG} & \text{CO$\textbf{W}$} & \text{R$\textbf{O}$W} & \text{$\textbf{R}$UG} \\ \text{BIG} & \text{RO$\textbf{W}$} & \text{N$\textbf{O}$W} & \text{$\textbf{S}$EA} \\ \text{TEA} & \text{NO$\textbf{W}$} & \text{B$\textbf{O}$X} & \text{$\textbf{T}$AB} \\ \text{NOW} & \text{BO$\textbf{X}$} & \text{F$\textbf{O}$X} & \text{$\textbf{T}$AR} \\ \text{FOX} & \text{FO$\textbf{X}$} & \text{R$\textbf{U}$G} & \text{$\textbf{T}$EA} \\ \end{array} 0COWDOGSEARUGROWMOBBOXTABBAREARTARDIGBIGTEANOWFOX​1SEATEAMOBTABDOGRUGDIGBIGBAREARTARCOWROWNOWBOXFOX​2TABBAREARTARSEATEADIGBIGMOBDOGCOWROWNOWBOXFOXRUG​3BARBIGBOXCOWDIGDOGEARFOXMOBNOWROWRUGSEATABTARTEA​​

8.3-2

插入排序和归并排序是稳定的。对相等的元素记录其原下标，额外开销 O ( n lg ⁡ n ) O(n\lg n) O(nlgn)时间和O(n)空间。

8.3-3

证明（来自参考答案）：

Basis: If d = 1 d = 1 d=1, there’s only one digit, so sorting on that digit sorts the array.

Inductive step: Assuming that radix sort works for d − 1 d - 1 d−1 digits, we’ll show that it works for d d d digits.

Radix sort sorts separately on each digit, starting from digit 1 1 1. Thus, radix sort of d d d digits, which sorts on digits 1 , … , d 1, \ldots, d 1,…,d is equivalent to radix sort of the low-order d − 1 d - 1 d−1 digits followed by a sort on digit d d d. By our induction hypothesis, the sort of the low-order d − 1 d - 1 d−1 digits works, so just before the sort on digit d d d, the elements are in order according to their low-order d − 1 d - 1 d−1 digits.

The sort on digit d d d will order the elements by their d d dth digit. Consider two elements, a a a and b b b, with dth digits a d a_d ad​ and b d b_d bd​ respectively.

If a d < b d a_d < b_d ad​<bd​, the sort will put a a a before b b b, which is correct, since a < b a < b a<b regardless of the low-order digits.

If a d > b d a_d > b_d ad​>bd​, the sort will put a a a after b b b, which is correct, since a > b a > b a>b regardless of the low-order digits.

If a d = b d a_d = b_d ad​=bd​, the sort will leave a a a and b b b in the same order they were in, because it is stable. But that order is already correct, since the correct order of a a a and b b b is determined by the low-order d − 1 d - 1 d−1 digits when their dth digits are equal, and the elements are already sorted by their low-order d − 1 d - 1 d−1 digits.

If the intermediate sort were not stable, it might rearrange elements whose d d dth digits were equal—elements that were in the right order after the sort on their lower-order digits.

8.3-4

可视为三位n进制数，进行特殊的基数排序。

8.3-5

解：d轮； 1 0 d 10^d 10d堆。

8.4 桶排序

8.4-1

略。。。

8.4-2

因为其中运用了插入排序作为子排序算法；可改为归并排序。

8.4-3

解： 3 2 \frac{3}{2} 23​; 1 1 1

8.4-4

提示：将 d i d_i di​按照 1 : 2 : . . . : n 1:\sqrt2:...:\sqrt n 1:2 ​:...:n ​划分为各桶。

8.4-5

思路：我觉得这题就是可以仿照8.4-4，找到一个桶的所有“划分分位”，将元素划分到各个桶间，然后就是类似于桶排序的步骤了。

思考题

8-1 （比较排序的概率下界）

（本题证明来自参考答案）

a.

For a comparison algorithm A A A to sort, no two input permutations can reach the same leaf of the decision tree, so there must be at least n ! n! n! leaves reached in T A T_A TA​, one for each possible input permutation. Since A A A is a deterministic algorithm, it must always reach the same leaf when given a particular permutation as input, so at most n ! n! n! leaves are reached (one for each permutation). Therefore exactly n ! n! n! leaves are reached, one for each input permutation.

These n ! n! n! leaves will each have probability 1 / n ! 1 / n! 1/n!, since each of the n ! n! n! possible permutations is the input with the probability 1 / n ! 1 / n! 1/n!. Any remaining leaves will have probability 0 0 0, since they are not reached for any input.

Without loss of generality, we can assume for the rest of this problem that paths leading only to 0 0 0-probability leaves aren’t in the tree, since they cannot affect the running time of the sort. That is, we can assume that T A T_A TA​ consists of only the n ! n! n! leaves labeled 1 / n ! 1 / n! 1/n! and their ancestors.

b.

If k > 1 k > 1 k>1, then the root of T T T is not a leaf. This implies that all of T T T's leaves are leaves in L T LT LT and R T RT RT. Since every leaf at depth h h h in L T LT LT or R T RT RT has depth h + 1 h + 1 h+1 in T T T, D ( T ) D(T) D(T) must be the sum of D ( L T ) D(LT) D(LT), D ( R T ) D(RT) D(RT), and k k k, the total number of leaves. To prove this last assertion, let d T ( x ) = d_T(x) = dT​(x)= depth of node x x x in tree T T T. Then,

D ( T ) = ∑ x ∈ T d T ( x ) = ∑ x ∈ L T d T ( x ) + ∑ x ∈ R T d T ( x ) = ∑ x ∈ L T ( d L T ( x ) + 1 ) + ∑ x ∈ R T ( d R T ( x ) + 1 ) = ∑ x ∈ L T d L T ( x ) + ∑ x ∈ R T d R T ( x ) + ∑ x ∈ T 1 = D ( L T ) + D ( R T ) + k . \begin{aligned} D(T) & = \sum_{x \in T} d_T(x) \\ & = \sum_{x \in LT} d_T(x) + \sum_{x \in RT} d_T(x) \\ & = \sum_{x \in LT} (d_{LT}(x) + 1) + \sum_{x \in RT} (d_{RT}(x) + 1) \\ & = \sum_{x \in LT} d_{LT}(x) + \sum_{x \in RT} d_{RT}(x) + \sum_{x \in T} 1 \\ & = D(LT) + D(RT) + k. \\ \end{aligned} D(T)​=x∈T∑​dT​(x)=x∈LT∑​dT​(x)+x∈RT∑​dT​(x)=x∈LT∑​(dLT​(x)+1)+x∈RT∑​(dRT​(x)+1)=x∈LT∑​dLT​(x)+x∈RT∑​dRT​(x)+x∈T∑​1=D(LT)+D(RT)+k.​

c.

To show that d ( k ) = min ⁡ 1 ≤ i ≤ k − 1 d ( i ) + d ( k − i ) + k d(k) = \min_{1\le i\le k - 1}{d(i) + d(k - i) + k} d(k)=min1≤i≤k−1​d(i)+d(k−i)+k we will show separately that

d ( k ) ≤ min ⁡ 1 ≤ i ≤ k − 1 d ( i ) + d ( k − i ) + k and d ( k ) ≥ min ⁡ 1 ≤ i ≤ k − 1 d ( i ) + d ( k − i ) + k . \begin{aligned} & d(k) \le \min_{1\le i\le k - 1}{d(i) + d(k - i) + k} \\ \text{and } & d(k) \ge \min_{1\le i\le k - 1}{d(i) + d(k - i) + k}. \end{aligned} and​d(k)≤1≤i≤k−1min​d(i)+d(k−i)+kd(k)≥1≤i≤k−1min​d(i)+d(k−i)+k.​

To show that d ( k ) ≤ min ⁡ 1 ≤ i ≤ k − 1 d ( i ) + d ( k − i ) + k d(k) \le \min_{1\le i\le k - 1}{d(i) + d(k - i) + k} d(k)≤min1≤i≤k−1​d(i)+d(k−i)+k, we need only show that d ( k ) ≤ d ( i ) + d ( k − i ) + k d(k) \le d(i) + d(k - i) + k d(k)≤d(i)+d(k−i)+k, for i = 1 , 2 , … , k − 1 i = 1, 2, \ldots, k - 1 i=1,2,…,k−1. For any i i i from 1 1 1 to k − 1 k - 1 k−1 we can find trees R T RT RT with i i i leaves and L T LT LT with k − i k - i k−i leaves such that D ( R T ) = d ( i ) D(RT) = d(i) D(RT)=d(i) and D ( L T ) = d ( k − i ) D(LT) = d(k - i) D(LT)=d(k−i). Construct T T T such that R T RT RT and L T LT LT are the right and left subtrees of T T T's root respectively. Then

d ( k ) ≤ D ( T ) (bydefinitionof d asmin D ( T ) value) = D ( R T ) + D ( L T ) + k (bypart(b)) = d ( i ) + d ( k − i ) + k . (bychoiceof R T and L T ) \begin{aligned} d(k) & \le D(T) & \text{(by definition of $d$ as min $D(T)$ value)} \\ & = D(RT) + D(LT) + k & \text{(by part (b))} \\ & = d(i) + d(k - i) + k. & \text{(by choice of $RT$ and $LT$)} \end{aligned} d(k)​≤D(T)=D(RT)+D(LT)+k=d(i)+d(k−i)+k.​(bydefinitionofdasminD(T)value)(bypart(b))(bychoiceofRTandLT)​

To show that d ( k ) ≥ min ⁡ 1 ≤ i ≤ k − 1 d ( i ) + d ( k − i ) + d d(k) \ge \min_{1\le i\le k - 1}{d(i) + d(k - i) + d} d(k)≥min1≤i≤k−1​d(i)+d(k−i)+d, we need only show that d ( k ) ≥ d ( i ) + d ( k − i ) + k d(k) \ge d(i) + d(k - i) + k d(k)≥d(i)+d(k−i)+k, for some i i i in 1 , 2 , … , k − 1 {1, 2, \ldots, k - 1} 1,2,…,k−1. Take the tree T T T with k k k leaves such that D ( T ) = d ( k ) D(T) = d(k) D(T)=d(k), let R T RT RT and L T LT LT be T T T's right and left subtree, respectively, and let i i i be the number of leaves in R T RT RT. Then k − i k - i k−i is the number of leaves in L T LT LT and

d ( k ) = D ( T ) (bychoiceof T ) = D ( R T ) + D ( L T ) + k (bypart(b)) ≥ d ( i ) + d ( k − i ) + k . (bydefinitionof d asmin D ( T ) value) \begin{aligned} d(k) & = D(T) & \text{(by choice of $T$)} \\ & = D(RT) + D(LT) + k & \text{(by part (b))} \\ & \ge d(i) + d(k - i) + k. & \text{(by definition of $d$ as min $D(T)$ value)} \end{aligned} d(k)​=D(T)=D(RT)+D(LT)+k≥d(i)+d(k−i)+k.​(bychoiceofT)(bypart(b))(bydefinitionofdasminD(T)value)​

Neither i i i nor k − i k - i k−i can be 0 0 0 (and hence 1 ≤ i ≤ k − 1 1 \le i \le k - 1 1≤i≤k−1), since if one of these were 0 0 0, either R T RT RT or L T LT LT would contain all k k k leaves of T T T, and that k k k-leaf subtree would have a D D D equal to D ( T ) − k D(T) - k D(T)−k (by part (b)), contradicting the choice of T T T as the k k k-leaf tree with the minimum D D D.

d.

Let f k ( i ) = i lg ⁡ i + ( k − i ) lg ⁡ ( k − i ) f_k(i) = i\lg i + (k - i)\lg(k - i) fk​(i)=ilgi+(k−i)lg(k−i). To find the value of i i i that minimizes f k f_k fk​, find the i i i for which the derivative of f k f_k fk​ with respect to i i i is 0 0 0:

f k ′ ( i ) = d d i ( i ln ⁡ i + ( k − i ) ln ⁡ ( k − i ) ln ⁡ 2 ) = ln ⁡ i + 1 − ln ⁡ ( k − i ) − 1 ln ⁡ 2 = ln ⁡ i − ln ⁡ ( k − i ) ln ⁡ 2 \begin{aligned} f_k'(i) & = \frac{d}{di} \Big(\frac{i\ln i + (k - i)\ln(k - i)}{\ln 2}\Big) \\ & = \frac{\ln i + 1 - \ln(k - i) - 1}{\ln 2} \\ & = \frac{\ln i - \ln(k - i)}{\ln 2} \end{aligned} fk′​(i)​=did​(ln2ilni+(k−i)ln(k−i)​)=ln2lni+1−ln(k−i)−1​=ln2lni−ln(k−i)​​

is 0 0 0 at i = k / 2 i = k / 2 i=k/2. To verify this is indeed a minimum (not a maximum), check that the second derivative of f k f_k fk​ is positive at i = k / 2 i = k / 2 i=k/2:

f k ′ ′ ( i ) = d d i ( ln ⁡ i − ln ⁡ ( k − i ) ln ⁡ 2 ) = 1 ln ⁡ 2 ( 1 i + 1 k − i ) . \begin{aligned} f_k''(i) & = \frac{d}{di}\Big(\frac{\ln i - \ln(k - i)}{\ln 2}\Big) \\ & = \frac{1}{\ln 2}\Big(\frac{1}{i} + \frac{1}{k - i}\Big). \end{aligned} fk′′​(i)​=did​(ln2lni−ln(k−i)​)=ln21​(i1​+k−i1​).​

f k ′ ′ ( k / 2 ) = 1 ln ⁡ 2 ( 2 k + 2 k ) = 1 ln ⁡ 2 ⋅ 4 k > 0 since k > 1 . \begin{aligned} f_k''(k / 2) & = \frac{1}{\ln 2}\Big(\frac{2}{k} + \frac{2}{k}\Big) \\ & = \frac{1}{\ln 2} \cdot \frac{4}{k} \\ & > 0 & \text{since $k > 1$}. \end{aligned} fk′′​(k/2)​=ln21​(k2​+k2​)=ln21​⋅k4​>0​sincek>1.​

Now we use substitution to prove d ( k ) = Ω ( k lg ⁡ k ) d(k) = \Omega(k\lg k) d(k)=Ω(klgk). The base case of the induction is satisfied because d ( 1 ) ≥ 0 = c ⋅ 1 ⋅ lg ⁡ 1 d(1) \ge 0 = c \cdot 1 \cdot \lg 1 d(1)≥0=c⋅1⋅lg1 for any constant c c c. For the inductive step we assume that d ( i ) ≥ c i lg ⁡ i d(i) \ge ci\lg i d(i)≥cilgi for 1 ≤ i ≤ k − 1 1 \le i \le k - 1 1≤i≤k−1, where c c c is some constant to be determined.

d ( k ) = min ⁡ 1 ≤ i ≤ k − 1 d ( i ) + d ( k − i ) + k ≥ min ⁡ 1 ≤ i ≤ k − 1 c ( i lg ⁡ i + ( k − i ) lg ⁡ ( k − i ) ) + k = min ⁡ 1 ≤ i ≤ k − 1 c f k ( i ) + k = c ( k 2 lg ⁡ k 2 ( k − k 2 ) lg ⁡ ( k − k 2 ) ) + k = c k lg ⁡ ( k 2 ) + k = c ( k lg ⁡ k − k ) + k = c k lg ⁡ k + ( k − c k ) ≥ c k lg ⁡ k if c ≤ 1 , \begin{aligned} d(k) & = \min_{1\le i\le k - 1} {d(i) + d(k - i) + k} \\ & \ge \min_{1\le i\le k - 1} {c(i\lg i + (k - i)\lg(k - i)) + k} \\ & = \min_{1\le i\le k - 1} {cf_k(i) + k} \\ & = c\Big(\frac{k}{2}\lg\frac{k}{2}\Big(k - \frac{k}{2}\Big)\lg\Big(k - \frac{k}{2}\Big)\Big) + k \\ & = ck\lg\Big(\frac{k}{2}\Big) + k \\ & = c(k\lg k - k) + k \\ & = ck\lg k + (k - ck) \\ & \ge ck\lg k & \text{if $c \le 1$}, \end{aligned} d(k)​=1≤i≤k−1min​d(i)+d(k−i)+k≥1≤i≤k−1min​c(ilgi+(k−i)lg(k−i))+k=1≤i≤k−1min​cfk​(i)+k=c(2k​lg2k​(k−2k​)lg(k−2k​))+k=cklg(2k​)+k=c(klgk−k)+k=cklgk+(k−ck)≥cklgk​ifc≤1,​

and so d ( k ) = Ω ( k lg ⁡ k ) d(k) = \Omega(k\lg k) d(k)=Ω(klgk).

e.

Using the result of part (d) and the fact that T A T_A TA​ (as modified in our solution to part (a)) has n ! n! n! leaves, we can conclude that

D ( T A ) ≥ d ( n ! ) = Ω ( n ! lg ⁡ ( n ! ) ) . D(T_A) \ge d(n!) = \Omega(n!\lg(n!)). D(TA​)≥d(n!)=Ω(n!lg(n!)).

D ( T A ) D(T_A) D(TA​) is the sum of the decision-tree path lengths for sorting all input permutations, and the path lengths are proportional to the run time. Since the n ! n! n! permutations have equal probability 1 / n ! 1 / n! 1/n!, the expected time to sort n n n random elements (1 input permutation) is the total time for all permutations divided by n ! n! n!:

Ω ( n ! lg ⁡ ( n ! ) ) n ! = Ω ( lg ⁡ ( n ! ) ) = Ω ( n lg ⁡ n ) . \frac{\Omega(n!\lg(n!))}{n!} = \Omega(\lg(n!)) = \Omega(n\lg n). n!Ω(n!lg(n!))​=Ω(lg(n!))=Ω(nlgn).

f.

We will show how to modify a randomized decision tree (algorithm) to define a deterministic decision tree (algorithm) that is at least as good as the randomized one in terms of the average number of comparisons.

At each randomized node, pick the child with the smallest subtree (the subtree with the smallest average number of comparisons on a path to a leaf). Delete all the other children of the randomized node and splice out the randomized node itself.

The deterministic algorithm corresponding to this modified tree still works, because the randomized algorithm worked no matter which path was taken from each randomized node.

The average number of comparisons for the modified algorithm is no larger than the average number for the original randomized tree, since we discarded the higher-average subtrees in each case. In particular, each time we splice out a randomized node, we leave the overall average less than or equal to what it was, because

the same set of input permutations reaches the modified subtree as before, but those inputs are handled in less than or equal to average time than before, and

the rest of the tree is unmodified.

The randomized algorithm thus takes at least as much time on average as the corresponding deterministic one. (We’ve shown that the expected running time for a deterministic comparison sort is Ω ( n lg ⁡ n ) \Omega(n\lg n) Ω(nlgn), hence the expected time for a randomized comparison sort is also Ω ( n lg ⁡ n ) \Omega(n\lg n) Ω(nlgn)).

8-2 （线性时间原址排序）

a.

解：计数排序。

b.

解：（仿）快速排序。

c.

解：插入排序。

d.

解：使用计数排序。

e.

解：同d；是稳定的。

8-3 （变长数据项的排序）

a.

思路：可以先对各元素的位数采用计数排序分成各“桶”，再在各“桶”内部采用基数排序。

b.

思路：在右侧补“0”直至与最长字符相齐。

8-4 （水壶）

a.

思路：依次对每一个红（蓝）壶，进行线性查找，找到与之大小相等的蓝（红）壶。

b.

证明思路：可用类似8.1节中的决策树进行证明。

c.

思路：随机找到一红壶→使用此红壶对蓝壶进行PARTITION→使用PARTITION返回的蓝壶（与红壶大小相等）对红壶进行PARTITION→在PARTITION后的前（后）部分中随机找到一红壶→使用此红壶对PARTITION后的前（后）部分蓝壶进行PARTITION→……

8-5 （平均排序）

a.

解：完全排序。

b.

解： 1，3，2，4，5，6，7，8，9，10。

c.

解：

“仅当”的证明：

∑ j = i i + k − 1 A [ j ] k ≤ ∑ j = i + 1 i + k A [ j ] k ⇕ A [ i ] + ∑ j = i + 1 i + k − 1 A [ j ] k ≤ ∑ j = i + 1 i + k − 1 A [ j ] + A [ i + k ] k ⇕ A [ i ] k ≤ A [ i + k ] k ⇕ A [ i ] ≤ A [ i + k ] \frac{\sum_{j=i}^{i+k-1}A[j]}{k} \le \frac{\sum_{j=i + 1}^{i+k}A[j]}{k} \\ \Updownarrow \\ \frac{A[i] + \sum_{j=i+1}^{i+k-1}A[j]}{k} \le \frac{\sum_{j=i+1}^{i+k-1}A[j] + A[i+k]}{k} \\ \Updownarrow \\ \frac{A[i]}{k} \le \frac{A[i+k]}{k} \\ \Updownarrow \\ A[i] \le A[i+k] k∑j=ii+k−1​A[j]​≤k∑j=i+1i+k​A[j]​⇕kA[i]+∑j=i+1i+k−1​A[j]​≤k∑j=i+1i+k−1​A[j]+A[i+k]​⇕kA[i]​≤kA[i+k]​⇕A[i]≤A[i+k]

反过来可证明“当”。

d.

思路：元素的下标对k取余可分为k组，每组有大概有n/k个数，对每组分别排序即可。

e.

证明思路：结合d与练习6.5-9可证明。

f.

证明思路：结合上面各题易证。

8-6（合并有序列表的下界）

a.

解： C 2 n n C_{2n}^n C2nn​

b.

证明：

2 2 n π n ( 1 + O ( 1 / n ) ) ≤ l ≤ 2 h \frac{2^{2n}}{\sqrt{\pi n}}(1 + O(1/n)) \le l \le 2^h πn ​22n​(1+O(1/n))≤l≤2h

h ≥ lg ⁡ ( 2 2 n π n ( 1 + O ( 1 / n ) ) ) = lg ⁡ 2 2 n − lg ⁡ π n + lg ⁡ ( 1 + O ( 1 / n ) ) = 2 n − o ( n ) \begin{aligned} h & \ge \lg\bigg(\frac{2^{2n}}{\sqrt{\pi n}}(1 + O(1/n))\bigg) \\ & = \lg{2^{2n}} - \lg\sqrt{\pi n} + \lg(1 + O(1/n)) \\ & = 2n - o(n) \end{aligned} h​≥lg(πn ​22n​(1+O(1/n)))=lg22n−lgπn ​+lg(1+O(1/n))=2n−o(n)​

c.

证明：如果我们不比较两个连续的元素，我们不知道哪个元素首先出现。 与其他元素相比，它们完全无法区分。我们无法确定哪一个应该在前。（注意，如果它们在同一个序列中，我们不需要比较它们，因为我们已经有了这些信息）。

d.

如果元素的排序顺序是 ⟨ a 1 , b 1 , a 2 , b 2 , … , a n , b n ⟩ \langle a_1, b_1, a_2, b_2, \ldots,a_n, b_n \rangle ⟨a1​,b1​,a2​,b2​,…,an​,bn​⟩，我们有两个序列 ⟨ a 1 , a 2 , … , a n ⟩ \langle a_1, a_2, \ldots,a_n \rangle ⟨a1​,a2​,…,an​⟩和 ⟨ b 1 , b 2 , … , b n ⟩ \langle b_1, b_2, \ldots, b_n \rangle ⟨b1​,b2​,…,bn​⟩，那么需要比较2n-1对元素。 处理这种情况的任何算法必须在最坏的情况下执行2n-1比较。

8-7 （0-1排序引理和列排序）

（0-1排序引理部分）

a.

0-1排序引理相关阅读

b.

0-1排序引理相关阅读

（列排序部分）

注：这题我考虑了好久。。。题干中的条件“s必须是r的因子”和“ r ≥ 2 s 2 r\geq2s^2 r≥2s2”很重要，现在我把算法每一步结束后输出的结果分析一下。

(1) 在第1步后，输出结果：顶部一些全0行，底部一些全1行，中间有一些脏行。

注：脏行个数不限制，可能是0（假设输入的每一列都是由相等比例的0和1组成的），也可能是r（假设输入的一些列是全0，一些列是全1）

(2) 在第2步后，输出结果：{一些全0行→最多1个脏行→一些全1行}→{一些全0行→最多1个脏行→一些全1行}→……（一共s个{}内的内容）

注：第(2)步运用到了条件“s必须是r的因子”，这个条件使得每一列都能转化为整数行，没有哪一行是掺杂了转置前两列的元素。

(3) 在第3步后，输出结果：如d所述。

注：只要理解了第(2)步，这一步很容易理解，脏行最多有s个。

(4) 在第4步后，输出结果：如e所述，且脏列最多只有2个。

注：第3步后存在的最多s脏行，产生了s×s的脏区域。e中所说的“按列读取”其实就相当于在第3步后“按行读取”，肯定会有 s 2 s^2 s2个元素组成的脏区域。又因为条件“ r ≥ 2 s 2 r\geq2s^2 r≥2s2”，脏列肯定不会超过2个。

(5) 在第5步后，输出结果：对第4步中可能存在的脏列进行排序。

注：如果第4步后脏列只有1个，其实在此时排序已完成；如果第4步后脏列有2个，则2个脏列必然相邻，且每个脏列的脏区不会超过一列的一半（因为条件“ r ≥ 2 s 2 r\geq2s^2 r≥2s2”；且前一脏列的脏区在后半部分，后一脏列的脏区在前半部分）。

但需要注意的是，此时排序并不一定完成，因为虽然对每一脏列进行了排序，但如果有2个脏列的话，前一脏列的末尾处的1和后一脏列开始处的0，拼接后，显然还是不符合排序的原则的。

(6) 在第6步和第7步后，输出结果：此时按列读取的数组已经是排好序的数组了。

注：这两步其实就是对“第4步后脏列有2个”的情况进行处理，将前一脏列的后半部分与后一脏列的前半部分组合成一个新列（因为每个脏列的脏区不会超过一列的一半，所以实际上数组中剩下所有的脏区域都在此时集中到新列里），再进行排序，这样实际上数组的排序已经完成（因为按列读取的话，新列就是数组唯一的脏区域，它前面只有0，后面只有1）。

(7) 在第8步后，输出结果就是最终输出结果。

c.

由于偶数步骤盲目地执行，我们可以怀疑算法中有一些遗忘的元素。如果我们用一个不经意的比较交换算法执行奇数步骤，那么列排序显然是遗忘的，我们可以应用0-1排序引理。由于我们可以将这些步骤视为“黑盒子”，因此我们可以将排序算法替换为产生相同结果的任何其他算法（即任何排序算法），并且生成的列排序仍然会排序。

d.

d、e、f可由上面的分析得出。

e.

d、e、f可由上面的分析得出。

f.

d、e、f可由上面的分析得出。

g.

思路：因为没有了条件“s必须是r的因子”，所以每一列都无法转化为整数行，因此必然有一些行掺杂了转置前两列的元素。

解：

现在第2步的输出结果变为{一些全0行→最多1个脏行→一些全1行→一些脏行}→{一些全0行→最多1个脏行→一些全1行→一些脏行}→……（一共s-1个{}内的内容）→一些全0行→最多1个脏行→一些全1行。

在{}中，第一个脏行是之前列内部存在的，而第二个脏行是之前两列元素掺杂形成的，因此第一个脏行共有最多s个，第二个脏行共有最多s-1个（最差情况下，每相邻两列的元素都会掺杂）。因此最多有2s-1个脏行，而第3步不会增加新的脏行，所以第3步后中间最多2s-1行脏行。

4 s 2 − 2 s 4s^2-2s 4s2−2s

h.

思路：两列元素掺杂形成脏区，必然是前一列的末尾是1，后一列的开始是0，改动后使得前后两列的衔接处元素相同即可。

解：奇数列升序排序，偶数列降序排序。这样可以使脏行数最多为s。

注：其实并不一定是衔接处的脏行被削除了，也有可能转置前前一列是全1，后一列是全0，这样转置后衔接处仍有脏行，但这样的话原列的内部必然没有脏区，所以列内部转置产生的脏行就没有了。