7.1 快速排序的描述
7.1.-1參照圖7-1的方法，說明PARTITION在數組A=<13,19,9,5,12,8,7,4,21,2,6,11>上的操作過程。
圖解：在一個樣例數組上的PARTITION操作過程。數組項A[r]是主元x=11,紅褐色陰影部分。淺綠部分的數組元素都在劃分的第一部分，其值都不大于x。深綠部分的元素都在劃分的第二部分，其值都大于x。無色的元素是還未分入這兩部分中的任意一個。
7.1-2 當數組A[p…r]中的元素都相同時，PARTITION傳回的q值是什麼？修改PARTITION,使得當數組A[p…r]中所有元素的值都相同時，q= ⌊(p+q)/2⌋ 。
1）傳回的是r
2)思路：讓主元等于首位的元素；i等于p+1，j=r。i指向的元素向左替換，j指向的元素向右替換，最後i和主元替換。
PARTITION(A,p,r)
{
x=A[p]
i=p+
for j=r to i=j
while(A[i]<x && i!=j)
i++
exchange A[i] and A[j]
i++
while(A[j]>x && i!=j)
j++
exchange A[i] and A[j]
j++
exchange A[i] and A[p]
}
7.1-3 請簡要的證明：在規模為n的子數組上，PARTITION的時間複雜度為θ（n）。
它的循環次數為r-p-1次，在規模為n的數組上，循環次數為n-2次
是以PARTITION的時間複雜度為θ（n）
7.1-4 如何修改QUICKSORT,使得它能夠以非遞增序進行排列？
控制遞增排序的是PARTITION而不是QUICKSORT部分，是以要對PARTITION函數進行修改，将裡面A[j]<=x變成A[j]>=x即可。
7.2 快速排序的性能
7.2-1 利用代入法證明： 正如7.2節開頭提到的那樣，遞歸式T(n)=T(n-1)+θ(n)的解為T（n）=θ（ n2 ）。
T(n)=c(n−1)2+n=cn2−2cn+1+n≤cn2c>1/2的時候成立
7.2-2 當數組A的所有元素都具有相同值時，QUICKSORT的時間複雜度是什麼
θ(n2)
7.2-3 證明：當數組A包含的元素不同，并且是按降序排列的時候，QUICKSORT的時間複雜度為θ（ n2 ）
第一次，劃分為0：n
第二次，劃分為0：n-1
……
最後進行次數 （1+n）n2
7.2-4 銀行一般會按照交易時間來記錄某一賬戶的交易情況。但是，很多人卻喜歡收到的銀行對賬單是按照支票号碼的順序來排列的。這是因為，人們通常都是按照支票号碼的順序來開出支票的，而商人也通常都是根據支票編号的順序兌付支票。這一問題是将按交易時間排序的序列轉換成按支票号排序的序列，它實質上是一個對幾乎有序的輸入序列進行排序的問題。請證明：在這個問題上，INSERTION-SORT 的性能往往要優于QUICKSORT？
QUICKSORT(a,p,r)
if p<r
q=PARTITION(A,p,r)
QUICKSORT(A,p,q-)
QUICKSORT(A,q+,r)
INSERTION-SORT(A)
for j= to A.length
key=A[j]
//Insert A[j] into the sorted sequence A[…j-]
i=j-
while i> and A[i]>key
A[i+]=A[i]
i=i-
A[i+]=key
假如支票序列是排好序的
但是INSERTION-SORT時間複雜度為n
而QUICKSORT時間複雜度為 n2
所有INSERTION-SORT的性能往往要優于QUICKSORT
7.2-5 假設快速排序的每一層所做的劃分的比例都是1-α：α，其中 0<α≤1/2 且是一個常數。試證明：在相應的遞歸樹中，葉節點的最小深度大約是-lgn/lgα ，最大深度大約是-lgn/lg(1-α)(無需考慮整數舍入問題)。
最小深度：設最大深度為m，每次向α分割方向下降，m次分割後僅剩1個元素 n*α^m = 1， α^m = 1/n ，兩邊取對數 mlgα = lg1-lgn ，m = -lgn/lgα
最大深度：同理 n*((1-α)^m) = 1， (1-α)^m = 1/n ，取對數 mlg(1-α) = -lgn 即 m = -lgn/lg(1-α)
7.3 快速排序的随機化版本
7.3-1 為什麼我們分析随機化算法的期望運作時間，而不是其最壞運作時間呢？
因為想快速排序這樣的算法，很少處于最壞運作時間。
7.3-2 在RANDOMIZED-QUICKSORT 的運作過程中，在最壞情況下，随機數生成器RANDOM 被調用了多少次？最好情況下呢？以θ的形式給出你的答案。
最壞情況下n-1次，θ（n）
最好情況下是lgn次，θ（lgn）
7.4 快速排序分析
7.4-1 證明：在遞歸式
T(n)=max0≤q≤n−1(T(q)+T(n−q−1))+θ(n)
中，T(n)=Ω（ n2 ）
用代入法證明：
T(n)=cq2+c(n−q−1)2+θ(n)T(n)≥c(n−q−1)2
是以T(n)=Ω（ n2 ）
7.4-2 證明：在最好的情況下，快速排序的運作時間為Ω（nlgn）。
最好的情況即每次都恰好均分，像二叉樹一樣nlgn。
7.4-3 證明：在q=0，1，…，n-1區間内，當q=0或q=n-1時， q2+(n−q−1)2 取得最大值。
設f=q2+(n−q−1)2，用配方法f=q22+(n−q−1)22+q(n−q−1)+q22+(n−q−1)22−q(n−q−1)f=(n−1)22+(2q−n+1)22由題意可知，當q=n−1時取得最小值當n=0時,q=n−1=−1,而q又是大于0的，不可能存在故當q=0，或q=n−1時，取得最大值。
7.4-4 證明：RANDOMIZED-QUICKSORT期望運作時間是Ω（nlgn）。
由書上可知:E[X]=∑i=1n−1∑j=i+1n2j−i+1E[X]=∑i=1n−1∑j=i+1n2j−i+1=∑i=1n−1∑k=1n−i2k+1≥∑i=1n−1∑k=2n−i+12k=∑i=1n−1Ω（lgn）=Ω（nlgn）
7.4-5 當輸入資料已經“幾乎有序”時，插入排序速度很快。在實際應用中，我們可以利用這一特點來提高快速排序的速度。當對一個長度小于k的子數組調用快速排序時，讓它不做任何排序就傳回。當上層的快速排序調用傳回後，對整個數組運作插入排序來完成排序過程。試證明：這一排序算法的期望時間複雜度為O（nk+nlg(n/k)）。分别從理論和實踐的角度說明我們應該如何選擇k。
此時快速排序的複雜度E[Xij]=∑i=k+1n∑j=i+k+1n2j−i+1E[Xij]=∑i=k+1n(∑m=1n−i2m+1−∑m=1k2m+1)≤∑i=k+1n(lgn−lgk)是以複雜度為O（nlgnk）
插入排序的運作時間對于長度為k的n/k個由快速排序已排好序的子數組來說，每個子數組的時間複雜度為O( k2 ),那麼n/k個就是O（ k2nk ）是以快速排序加插入排序的時間複雜度是 O（nlgnk） k的理論值是k∈（ n√,n+12 ）。