7.1 快速排序的描述

7.1-1

解：

13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11

9, 19, 13, 5, 12, 8, 7, 4, 21, 2, 6, 11

9, 5, 13, 19, 12, 8, 7, 4, 21, 2, 6, 11

9, 5, 8, 19, 12, 13, 7, 4, 21, 2, 6, 11

9, 5, 8, 7, 12, 13, 19, 4, 21, 2, 6, 11

9, 5, 8, 7, 4, 13, 19, 12, 21, 2, 6, 11

9, 5, 8, 7, 4, 2, 19, 12, 21, 13, 6, 11

9, 5, 8, 7, 4, 2, 6, 12, 21, 13, 19, 11

9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12

return 8

7.1-2

解：r；可以检查所有元素的值都相同的情况

7.1-3

易证。

7.1-4

解：第四行的≤改为≥。

7.2 快速排序的性能

7.2-1

证明：

T(n)≥c1(n−1)2+cn=c1n2−2c1n+c1+cn≥c1n2T(n)\geq c_1(n-1)^2+cn=c_1n^2 - 2c_1n+c_1+cn\geq c_1n^2T(n)≥c1​(n−1)2+cn=c1​n2−2c1​n+c1​+cn≥c1​n2

(c−2c1)n+c1≥0(c-2c_1)n+c_1\geq 0(c−2c1​)n+c1​≥0

c1≤c2c_1 ≤ \frac{c}{2}c1​≤2c​

T(n)≤c2(n−1)2+cn=c2n2−2c2n+c2+cn≤c2n2T(n) ≤ c_2(n-1)^2 + cn = c_2n^2 - 2c_2n + c_2 + cn ≤ c_2n^2T(n)≤c2​(n−1)2+cn=c2​n2−2c2​n+c2​+cn≤c2​n2

(c−2c2)n+c2≤0(c - 2c_2)n + c_2\leq 0(c−2c2​)n+c2​≤0

c2≥c2c_2 ≥ \frac{c}{2}c2​≥2c​

……

7.2-2

解：Θ(n2)Θ(n^2)Θ(n2)

7.2-3

证明（翻译自参考答案）：所有元素降序排列时我们运行的是“最坏情况PARTITION”。它每一步只将要考虑的子数组大小减1，运行时间Θ(n2)Θ(n^2)Θ(n2)。

7.2-4

本题证明翻译自/07/02/04.html

证明：

一个简单直观的论证就足够了。

数组排序越多，插入排序的工作量就越少。即，INSERTION-SORT是Θ(n+d)，其中d是阵列中的逆序对个数。 在上面的例子中，逆序对往往很少，因此插入排序将接近线性。

另一方面，如果PARTITION确实选择了不在逆序对中的元素，它将产生一个空分区。由于存在逆序对很少，QUICKSORT很可能产生空分区。

7.2-5

证明：

（1）最小深度：

αmn=1

m=-logαn=-lgn/lgα

（2）最大深度：

（1-α)Mn=1

M=-lgn/lg(1-α)

7.2-6

证明：

设nln_lnl​和nr_rr​代表左右两边的比例，更均衡表示∣nl−nr∣&lt;1−2α|n_l-n_r| &lt; 1-2α∣nl​−nr​∣<1−2α

当0&lt;nl&lt;α0&lt;n_l&lt;α0<nl​<α时，∣nl−nr∣&gt;1−2α|n_l-n_r| &gt; 1-2α∣nl​−nr​∣>1−2α

当α&lt;nl&lt;1−αα&lt;n_l&lt;1-αα<nl​<1−α时，∣nl−nr∣&lt;1−2α|n_l-n_r| &lt; 1-2α∣nl​−nr​∣<1−2α

当1−α&lt;nl&lt;11-α&lt;n_l&lt;11−α<nl​<1时，∣nl−nr∣&gt;1−2α|n_l-n_r| &gt; 1-2α∣nl​−nr​∣>1−2α

而nln_lnl​是均匀分布的，所以p≈1−2αp≈1-2αp≈1−2α

7.3 快速排序的随机化版本

7.3-1

随机化算法遭遇最坏情况的概率很小。

7.3-2

解：Θ(n)Θ(n)Θ(n)；Θ(n)Θ(n)Θ(n)。

7.4 快速排序分析

7.4-1

证明：

T(n)≥c[0+(n−1)2]+Θ(n)≥cn2T(n) ≥ c[0+(n-1)^2]+Θ(n) ≥ cn^2T(n)≥c[0+(n−1)2]+Θ(n)≥cn2

cn2−2cn+c+c′n≥cn&lt;2cn^2-2cn+c+c&#x27;n ≥ cn&lt;^2cn2−2cn+c+c′n≥cn<2

只要c′&gt;2cc&#x27; &gt; 2cc′>2c，……

7.4-2

证明思路：递归式为T(n)=2T(n/2)+Θ(n)T(n)=2T(n/2)+Θ(n)T(n)=2T(n/2)+Θ(n)，然后用主定理即可。

7.4-3

证明：

f(q)=q2+(n−q−1)2=q2+(n−1)2−2(n−1)q+q2=2q2−2(n−1)q+(n−1)2f(q)=q^2+(n-q-1)^2=q^2+(n-1)^2-2(n-1)q+q^2=2q^2-2(n-1)q+(n-1)^2f(q)=q2+(n−q−1)2=q2+(n−1)2−2(n−1)q+q2=2q2−2(n−1)q+(n−1)2

f′(q)=4q−2(n−1)f&#x27;(q)=4q-2(n-1)f′(q)=4q−2(n−1)

令f′(q)=0令f&#x27;(q)=0令f′(q)=0

q=n−12q=\frac{n-1}{2}q=2n−1​

当q&lt;n−12时，f′(q)&lt;0；当n−12时，f′(q)&gt;0当q&lt;\frac{n-1}{2}时，f&#x27;(q)&lt;0；当\frac{n-1}{2}时，f&#x27;(q)&gt;0当q<2n−1​时，f′(q)<0；当2n−1​时，f′(q)>0

f(0)=(n−1)2=f(n−1)，证毕。f(0)=(n-1)^2=f(n-1)，证毕。f(0)=(n−1)2=f(n−1)，证毕。

7.4-4

证明：

E[X]=∑i=1n−1∑j=i+1n[2j−i+1]E[X]=\sum_{i=1}^{n−1} ∑_{j=i+1}^{n}[\frac{2}{j−i+1}]E[X]=∑i=1n−1​∑j=i+1n​[j−i+12​]

=∑i=1n−1∑k=1n−i2k+1]= \sum_{i=1}^{n−1}\sum_{k=1}^{n−i}\frac{2}{k+1}]=∑i=1n−1​∑k=1n−i​k+12​]

≥∑i=1n−1∑k=1n−i22k]\geq\sum_{i=1}^{n−1} \sum_{k=1}^{n−i}\frac{2}{2k}]≥∑i=1n−1​∑k=1n−i​2k2​]

≥∑i=1n−1Ω(lgn)]\geq \sum_{i=1}^{n−1}\Omega(lgn)]≥∑i=1n−1​Ω(lgn)]

=Ω(nlgn)=\Omega(nlgn)=Ω(nlgn)

7.4-5

cqnlg⁡n≥cink+cqnlg⁡(n/k)cqlg⁡n≥cik+cqlg⁡n−cqlg⁡klg⁡k≥cicqkc_qn\lg{n} \ge c_ink + c_qn\lg(n/k) \\ c_q\lg{n} \ge c_ik + c_q\lg{n} - c_q\lg{k} \\ \lg{k} \ge \frac{c_i}{c_q}kcq​nlgn≥ci​nk+cq​nlg(n/k)cq​lgn≥ci​k+cq​lgn−cq​lgklgk≥cq​ci​​k

在理论中可以按上述过程确定k，而在实践中可以试出k。

7.4-6

解：假设0&lt;α≤1/20 &lt; \alpha \le 1/20<α≤1/2

P=6α2−4α3=2α2(3−2α)P = 6\alpha^2 - 4\alpha^3 = 2\alpha^2(3 - 2\alpha)P=6α2−4α3=2α2(3−2α)

思考题

7-1 （Hoare划分的正确性）

a.

解：

13(i), 19, 9, 5, 12, 8, 7, 4, 11, 2, 6(j), 21

6, 19(i), 9, 5, 12, 8, 7, 4, 11, 2(j), 13, 21

6, 2, 9, 5, 12, 8, 7, 4, 11(j), 19(i), 13, 21

b.

证明思路：该过程的初始化和循环条件将i和j控制在数组下标p和r的范围内。

c.

同b。

d.

证明：

循环不变式：在比较i和j的条件之前，所有元素A[p…i-1]≤x和A[j+1…r]≥x。

初始化：这两个重复块就是这种情况。

保持：通过交换A[i]和A[j]，我们得到A[p…i]≤x和A[j…r]≥x。递增i和递减j保持这个不变量。

终止：当i≥j时，循环终止。不变量仍然在终止时保持。

e.

解：

HOARE-QUICESORT(A, p, r)if p< rq = HOARE-PARTITION(A, p, r)HOARE-QUICKSORT(A, p, q-1)HOARE-QUICKSORT(A, q+1, r)

7-2 （针对相同元素值的快速排序）

a.

解：Θ(n2)Θ(n^2)Θ(n2)

b.

解：

PARTITION'(A, p, r)t = PARTITION(A, p, r)q = tfor j = t-1 downto pif A[j] == A[t]q = q - 1exchange A[j] with A[q]return q, t

c.

解：

RANDOMIZED-PARTITION'(A, p, r)i = RANDOM(p, r)exchange A[i] with A[r]return PARTITION'(A, p, r)

RANDOMIZED-QUICKSORT'(A, p, r)if p < rq, t = RANDOMIZED-PARTITION'(A, p, r)RANDOMIZED-QUICKSORT'(A, p, q-1)RANDOMIZED-QUICKSORT'(A, t+1, r)

d.

思路：将zij定义为数组A中第i小的元素中的一个。

7-3 （另一种快速排序的分析方法）

a.

解：E[Xi] = 1/n

b.

证明：让第q小元素成为主元。有n种可能的选择，每种都有Xq的概率。每个都将通过在q-1和n-q两个部分中分块并添加线性因子来解决问题。

c.

证明：

E[T(n)]=E[∑q=1nXqT(q−1)+T(n−q)+Θ(n)]E[T(n)] = E[\sum_{q=1}^{n} X_qT(q-1)+T(n-q)+\Theta(n)]E[T(n)]=E[∑q=1n​Xq​T(q−1)+T(n−q)+Θ(n)]

=∑q−1nE(Xq)E[T(q−1)+T(n−q)+Θ(n)]=\sum_{q-1}^{n}E(X_q)E[T(q-1)+T(n-q)+\Theta(n)]=∑q−1n​E(Xq​)E[T(q−1)+T(n−q)+Θ(n)]

=1n∑q=1nE[T(q−1)+T(n−q)]+Θ(n)=\frac {1}{n} \sum_{q=1}^{n}E[T(q-1)+T(n-q)]+\Theta(n)=n1​∑q=1n​E[T(q−1)+T(n−q)]+Θ(n)

=2n∑q=2n−1E[T(q)]+Θ(n)=\frac {2}{n} \sum_{q=2}^{n-1}E[T(q)]+\Theta(n)=n2​∑q=2n−1​E[T(q)]+Θ(n)

d.

证明：

∑k=2n−1klgk=∑k=2⌈n2⌉−1klgk+∑k=⌈n2⌉n−1klgk\sum_{k=2}^{n-1}klgk=\sum_{k=2}^{\lceil\frac {n}{2}\rceil-1}klgk+\sum_{k=\lceil\frac {n}{2}\rceil}^{n-1}klgk∑k=2n−1​klgk=∑k=2⌈2n​⌉−1​klgk+∑k=⌈2n​⌉n−1​klgk

≤∑k=1n2klgn2+∑k=n2n−1klgn\leq\sum_{k=1}^{\frac {n}{2}}klg\frac{n}{2}+\sum_{k=\frac {n}{2}}^{n-1}klgn≤∑k=12n​​klg2n​+∑k=2n​n−1​klgn

=lgn2⋅n2+2n8+lgn⋅3n2−2n8=lg\frac{n}{2}\cdot\frac{n^2+2n}{8}+lgn\cdot\frac{3n^2-2n}{8}=lg2n​⋅8n2+2n​+lgn⋅83n2−2n​

=n28lgn2+3n28lgn+n4lgn2−n4lgn=\frac{n^2}{8}lg\frac{n}{2}+\frac{3n^2}{8}lgn+\frac{n}{4}lg\frac{n}{2}-\frac{n}{4}lgn=8n2​lg2n​+83n2​lgn+4n​lg2n​−4n​lgn

≤n28lgn−n28lg2+3n28lgn=n22lgn−n28\leq\frac{n^2}{8}lgn-\frac{n^2}{8}lg2+\frac{3n^2}{8}lgn=\frac{n^2}{2}lgn-\frac{n^2}{8}≤8n2​lgn−8n2​lg2+83n2​lgn=2n2​lgn−8n2​

e.

证明：

E[T(n)]=2n∑q=2n−1E[T(q)]+Θ(n)E[T(n)]=\frac{2}{n}\sum_{q=2}^{n-1}E[T(q)]+\Theta(n)E[T(n)]=n2​∑q=2n−1​E[T(q)]+Θ(n)

≤2n∑q=2n−1aq⋅lgq+Θ(n)\leq\frac{2}{n}\sum_{q=2}^{n-1}aq\cdot lgq+\Theta(n)≤n2​∑q=2n−1​aq⋅lgq+Θ(n)

≤2an(n22lgn−n28)+Θ(n)\leq\frac{2a}{n}(\frac{n^2}{2}lgn-\frac{n^2}{8})+\Theta(n)≤n2a​(2n2​lgn−8n2​)+Θ(n)

≤anlgn−an4+Θ(n)\leq anlgn-\frac{an}{4}+\Theta(n)≤anlgn−4an​+Θ(n)

≤anlgn\leq anlgn≤anlgn

7-4 （快速排序的栈深度）

a.

证明：由两次递归调用改为一次递归调用加一次循环递归调用，而那一次循环递归调用其实就是原本的第二次递归调用（参数相同，只是函数名不一样了）。

b.

解：按升序排列输入，需调用n次。

c.

解：

TAIL-RECURSIVE-QUICKSORT(A, p, r)while p < rq = PARTITION(A, p, r)if q <= (p + r) / 2TAIL-RECURSIVE-QUICKSORT(A, p, q-1)p = q + 1elseTAIL-RECURSIVE-QUICKSORT(A, q+1, r)r = q - 1

7-5 （三数取中划分）

a.

解：pi=A33(i−1)(n−i)n(n−1)(n−2)=6(i−1)(n−i)n(n−1)(n−2)p_i=\frac{A_3^3(i-1)(n-i)}{n(n-1)(n-2)}=\frac{6(i-1)(n-i)}{n(n-1)(n-2)}pi​=n(n−1)(n−2)A33​(i−1)(n−i)​=n(n−1)(n−2)6(i−1)(n−i)​

b.

解：px1n=6(n2−1)(n−n2)n(n−1)(n−2)=3n(n−2)2(n−1)(n−2)=3n2(n−1)\frac{p_x}{\frac{1}{n}}=\frac{6(\frac{n}{2}-1)(n-\frac{n}{2})}{n(n-1)(n-2)}=\frac{3n(n-2)}{2(n-1)(n-2)}=\frac{3n}{2(n-1)}n1​px​​=n(n−1)(n−2)6(2n​−1)(n−2n​)​=2(n−1)(n−2)3n(n−2)​=2(n−1)3n​

limn→∞px1n=32lim_{n\rightarrow{\infty}}\frac{p_x}{\frac{1}{n}}=\frac{3}{2}limn→∞​n1​px​​=23​

增加了12\frac{1}{2}21​。

c.

解：

p′=∑i=n32n3pi=∫n32n36(i−1)(n−i)n(n−1)(n−2)di=13n27(n−2)→1327p&#x27;=\sum_{i=\frac{n}{3}}^{\frac{2n}{3}}p_i=\int_{\frac{n}{3}}^{\frac{2n}{3}}\frac{6(i-1)(n-i)}{n(n-1)(n-2)}di=\frac{13n}{27(n-2)}\rightarrow\frac{13}{27}p′=∑i=3n​32n​​pi​=∫3n​32n​​n(n−1)(n−2)6(i−1)(n−i)​di=27(n−2)13n​→2713​

d.

证明思路：最好情况仍是Ω(nlgn)\Omega(nlgn)Ω(nlgn)。

7-6 （对区间的模糊排序）

思路：本题是对区间的模糊排序，可以理解为对于两个区间有三种不同的状态：1）区间1的右端在区间2的左端的左方，即区间1产生的元素必定小于区间2产生的元素；2）区间1的右端在区间2的左端的右方，且区间1的左端在区间2的右端的左方，即两区间有重叠部分，产生的元素可能大于或等于或小于；3）区间1的左端在区间2的右端的右方，即区间1产生的元素必定大于区间2产生的元素。这三种情况分别对应非模糊排序的小于、等于、大于三种情况。

a.

解：

FUSSY-SORT(I[2]/*每个区间都由两个值表示，所以是二维数组*/, p, r)if p < rq, t = RANDOM-PARTITION(I[2], p, r) // 这里借鉴了思考题7-2的思路FUSSY-SORT(I[2], p, q-1)p = t + 1 // 这里借鉴了思考题7-4的思路

RANDOM-PARTITION(I[2], p, r)key = RANDOM(p, r)exchange I[key][*] with I[r][*]a = I[r][1]b = I[r][2]i = p - 1j = r + 1for k = p to r-1if I[k][2] <= ai = i + 1exchange I[k][*] with I[i][*]else if I[k][1] >= bj = j - 1exchange I[k][*] with I[j][*]elsea = max(a, I[k][1])b = min(b, I[k][2])return (i+1), (j-1)

b.

证明思路：随着重叠增加，一次分区后剩余需要排列的部分会减少，当所有区间都有重叠时，只需分区一次。