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)\ge c_1(n?1{)}^2+cn=c_1{n}^2?2c_{1}n+c_1+cn\ge c_1{n}^2$
$(c?2c_1)n+c_1\ge 0$
$c_1\le \frac{c}{2}$
$T(n)\le c_2(n?1{)}^2+cn=c_2{n}^2?2c_{2}n+c_2+cn\le c_2{n}^2$
$(c?2c_2)n+c_2\le 0$
$c_2\ge \frac{c}{2}$
……

7.2-2

解：$\Theta (n^2)$

7.2-3

證明（翻譯自參考答案）：所有元素降序排列時我們運行的是“最壞情況PARTITION”。它每一步只將要考慮的子數組大小減1，運行時間$\Theta (n^2)$。

7.2-4

本題證明翻譯自https://ita.skanev.com/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

證明：
設$n_l$和n${}_r$代表左右兩邊的比例，更均衡表示$|n_l?n_r|<1?2\alpha$
當$0<n_l<\alpha$時，$|n_l?n_r|>1?2\alpha$
當$\alpha <n_l<1?\alpha$時，$|n_l?n_r|<1?2\alpha$
當$1?\alpha <n_l<1$時，$|n_l?n_r|>1?2\alpha$
而$n_l$是均勻分布的，所以$p\approx 1?2\alpha$

7.3 快速排序的隨機化版本

7.3-1

隨機化算法遭遇最壞情況的概率很小。

7.3-2

解：$\Theta (n)$；$\Theta (n)$。

7.4 快速排序分析

7.4-1

證明：
$T(n)\ge c[0+(n?1{)}^2]+\Theta (n)\ge c{n}^2$
$c{n}^2?2cn+c+c^{\prime }n\ge cn{<}^2$
只要$c^{\prime }>2c$，……

7.4-2

證明思路：遞歸式為$T(n)=2T(n/2)+\Theta (n)$，然后用主定理即可。

7.4-3

證明：
$f(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{)}^2$
$f^{\prime }(q)=4q?2(n?1)$
$令f^{\prime }(q)=0$
$q=\frac{n?1}{2}$
$當q<\frac{n?1}{2}時，f^{\prime }(q)<0；當\frac{n?1}{2}時，f^{\prime }(q)>0$
$f(0)=(n?1{)}^2=f(n?1)，證畢。$

7.4-4

證明：
$E[X]={\sum }_{i=1}^{n?1}{\sum }_{j=i+1}^n[\frac{2}{j?i+1}]$
$={\sum }_{i=1}^{n?1}{\sum }_{k=1}^{n?i}\frac{2}{k+1}]$
$\ge {\sum }_{i=1}^{n?1}{\sum }_{k=1}^{n?i}\frac{2}{2k}]$
$\ge {\sum }_{i=1}^{n?1}\Omega (lgn)]$
$=\Omega (nlgn)$

7.4-5

$$\begin{gathered} c_{q}n\lg n\ge c_{i}nk+c_{q}n\lg (n/k) \\ {c}_q\lg n\ge c_{i}k+c_q\lg n?c_q\lg k \\ \lg k\ge \frac{c_i}{c_q}k \end{gathered}$$
在理論中可以按上述過程確定k，而在實踐中可以試出k。

7.4-6

解：假設$0<\alpha \le 1/2$
$P=6{\alpha }^2?4{\alpha }^3=2{\alpha }^2(3?2\alpha )$

思考題

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.

解：$\Theta (n^2)$

b.

解：

PARTITION'(A, p, r) t = PARTITION(A, p, r) q = t for 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.

思路：將z_ij定義為數組A中第i小的元素中的一個。

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

a.

解：E[X_i] = 1/n

b.

證明：讓第q小元素成為主元。有n種可能的選擇，每種都有X_q的概率。每個都將通過在q-1和n-q兩個部分中分塊并添加線性因子來解決問題。

c.

證明：
$E[T(n)]=E[{\sum }_{q=1}^n{X}_{q}T(q?1)+T(n?q)+\Theta (n)]$
$={\sum }_{q?1}^{n}E(X_q)E[T(q?1)+T(n?q)+\Theta (n)]$
$=\frac{1}{n}{\sum }_{q=1}^{n}E[T(q?1)+T(n?q)]+\Theta (n)$
$=\frac{2}{n}{\sum }_{q=2}^{n?1}E[T(q)]+\Theta (n)$

d.

證明：
${\sum }_{k=2}^{n?1}klgk={\sum }_{k=2}^{?\frac{n}{2}??1}klgk+{\sum }_{k=?\frac{n}{2}?}^{n?1}klgk$
$\le {\sum }_{k=1}^{\frac{n}{2}}klg\frac{n}{2}+{\sum }_{k=\frac{n}{2}}^{n?1}klgn$
$=lg\frac{n}{2}?\frac{n^2+2n}{8}+lgn?\frac{3n^2?2n}{8}$
$=\frac{n^2}{8}lg\frac{n}{2}+\frac{3n^2}{8}lgn+\frac{n}{4}lg\frac{n}{2}?\frac{n}{4}lgn$
$\le \frac{n^2}{8}lgn?\frac{n^2}{8}lg2+\frac{3n^2}{8}lgn=\frac{n^2}{2}lgn?\frac{n^2}{8}$

e.

證明：
$E[T(n)]=\frac{2}{n}{\sum }_{q=2}^{n?1}E[T(q)]+\Theta (n)$
$\le \frac{2}{n}{\sum }_{q=2}^{n?1}aq?lgq+\Theta (n)$
$\le \frac{2a}{n}(\frac{n^2}{2}lgn?\frac{n^2}{8})+\Theta (n)$
$\le anlgn?\frac{an}{4}+\Theta (n)$
$\le 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.

解：$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)}$

b.

解：$\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)}$
$li{m}_{n\to \infty }\frac{p_x}{\frac{1}{n}}=\frac{3}{2}$
增加了$\frac{1}{2}$。

c.

解：
$p^{\prime }={\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)}\to \frac{13}{27}$

d.

證明思路：最好情況仍是$\Omega (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 - 1 j = r + 1 for 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.

證明思路：隨著重疊增加，一次分區后剩余需要排列的部分會減少，當所有區間都有重疊時，只需分區一次。

總結

以上是生活随笔為你收集整理的《算法导论》第三版第7章 快速排序 练习思考题 个人答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。