第7章快速排序 · 《算法導論》答案

# 一、概念快速排序是基于分治模式的，選擇一個數作為主元，經過一遍掃描，所有小于主元的數放在主元的左邊，大于主元的數放在主元的右邊，這樣就劃分成了兩組數據。然后對兩組數分別進行快排。快排的運行時間與劃分是否對稱有關，關鍵是如何選擇主元。最壞情況下，時間復雜度是O(n^2)，最好情況下，時間是O(nlgn) # 二、程序 [頭文件](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/include/chapter7/quickSort.h) [算法過程](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/src/chapter7/quickSort.cpp) [測試](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/tst/chapter7/quickSortTest.cpp) # 三、練習 ### 7.1 快速排序的描述 ##### 7.1-1 A = {13 19 9 5 12 8 7 4 21 2 6 11} ==> A = {9 5 8 7 4 2 6 11 21 13 19 12} ==> A = {5 4 2 6 9 8 7 11 21 13 19 12} ==> A = {2 4 5 6 9 8 7 11 21 13 19 12} ==> A = {2 4 5 6 9 8 7 11 21 13 19 12} ==> A = {2 4 5 6 7 8 9 11 21 13 19 12} ==> A = {2 4 5 6 7 8 9 11 21 13 19 12} ==> A = {2 4 5 6 7 8 9 11 12 13 19 21} ==> A = {2 4 5 6 7 8 9 11 12 13 19 21} ==> A = {2 4 5 6 7 8 9 11 12 13 19 21} ##### 7.1-2 返回r ##### 7.1-2 修改PARTITION(A, p, r)，增加對A[i]==x時的處理。對于A[i]==x的數據，一半放在x左邊，一半放在x右邊 [算法過程](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/src/chapter7/Exercise7_1_2.cpp) [測試](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/tst/chapter7/Exercise7_1_2Test.cpp) ##### 7.1-3 PARTITION()的具體過程如下： (1)x<-A[r]，O(1) (2)遍歷數組，O(n) (3)exchange，O(1) 因此運行時間為O(n) #####7.1-4 修改PARTITION(A, p, r)，把L4改為do if A[j] >= x ### 7.2 快速排序的性能 ##### 7.2-1 見《算法導論》7.4.1。我的方法： ``` T(n) = T(n-1) + O(n) T(n-1) = T(n-2) + O(n-1) …… = …… + …… T(2) = T(1) + O(2) ------------------------ T(n) = T(1) + O(n) + O(n-1) + …… + O(2) = O(n^2) ``` ##### 7.2-2 O(n^2) ##### 7.2-3 當數組A包含不同元素且按降序排序時，每次劃分會劃分成n-1個元素和1個元素這兩個區域，即最壞情況。因此時間為O(n^2) ##### 7.2-4 基本有序的數列用快排效率較低 ##### 7.2-5 若第一層的元素個數是n，那么會劃分成n(1-a)個元素和na個元素這兩個區域。0<a<=1/2 ==> na<=n(1-a)，因此只考慮n(1-a)。第t層元素個數為na^(t-1)。當na^(t-1)=1時劃分結束。解得t=-lgn/lg(1-a)+1，大約是-lgn/lg(1-a)。 ##### 7.2-6 可參考http://blog.163.com/kevinlee_2010/blog/static/16982082020112585946451/，不過我沒看懂 ### 7.3 快速排序的隨機化版本 ##### 7.3-1 隨機化不是為了提高最壞情況的性能，而是使最壞情況盡量少出現 ##### 7.3-2 最壞情況下，n個元素每次都劃分成n-1和1個，1個不用再劃分，所以O(n)次最好情況下，每次從中間劃分，遞推式N(n)=1+2*N(n/2)=O(n) ### 7.4 快速排序的分析 ##### 7.4-1 沒有找到關于這幾個符號的定義 ##### 7.4-2 見《算法導論》P88最佳情況劃分 ##### 7.4-3 令f(q) = q^2 + (n-q-1)^2 = 2q^2 + 2(1-n)q + (n-1)^2 這是一個關于q的拋物線，且開口向上。因此q的取值離對稱軸越遠，f(q)的值就越大。對稱軸為q = -b/2a = (n-1)/2 當q=0或q=n-1時取得最大值 ##### 7.4-4 見《算法導論》P7.4.2 ##### 7.4-5 [算法過程](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/src/chapter7/Exercise7_4_5.cpp) # 四、思考題 ### 7-1 Hoare劃分的正確性 a） A = {13 19 9 5 12 8 7 4 11 2 6 21} ==> A = {6 19 9 5 12 8 7 4 11 2 13 21} ==> A = {6 2 9 5 12 8 7 4 11 19 13 21} ==> A = {4 2 9 5 12 8 7 6 11 19 13 21} ==> A = {4 2 5 9 12 8 7 6 11 19 13 21} ==> A = {2 4 5 9 12 8 7 6 11 19 13 21} ==> A = {2 4 5 6 12 8 7 9 11 19 13 21} ==> A = {2 4 5 6 7 8 12 9 11 19 13 21} ==> A = {2 4 5 6 7 8 9 12 11 19 13 21} ==> A = {2 4 5 6 7 8 9 12 11 13 19 21} b)自己寫的，很亂，湊合看吧主要證明以下幾點：（1）do repeat j<-j-1 until A[j]<=x 這個repeat中，第一次執行L6時p<=j<=r，最后一次執行L6時p<=j<=r 證明： 1.第一次執行L6時p<=j<=r。為了區分，j'=j-1，L6中的j用j'表示。第一次進入while循環時，j=r+1，j'=r，滿足p<=j<=r。若不是第一次進入while循環，j<=r且j>p。因為如果j=p，在上一次while循環中L9的if不能通過，已經return了。因此p<=j<r-1，滿足p<=j<=r。 2.最后一次執行L6時p<=j<=r，即要證明在A[p..r]中存在j'滿足j'<=j且A[j]<=x 若第一次進入while循環，j'=p滿足條件若不是第一次進入while循環，在上一次while循環中交換過去的那個元素滿足條件（2）do repeat i<i+1 until A[i]>=x 這個repeat中，第一次執行L8時p<=i<=r，最后一次執行L8時p<=i<=r 證明：證明方法與（1）類似 c)根據b可知返回值p<=j<=r，這里只需證明j!=r 若A[r]>x,L5和L6的循環不會在j=r時停止，因此返回值j!=r 若A[r]<=x，只有在第一次進入while循環時，L5和L6的循環在j=r時停止。因為是第一次進入while循環，A[i]=A[p]=x，L7和L8的循環會在i=p時停止。顯然會第二次進入while循環，此時j<r，因此返回值j!=r d)題目寫錯了，應該是A[p..j]中的每個元素都小于或等于A[j+1..r]中的每個元素結束時，A[p..i-1]中的元素都小于x，A[j+1..r]中的元素都大于x，命題得證 e) ```c++ int Hoare_Partition(int *A, int p, int r) { int x = A[p], i = p - 1, j = r + 1; while(true) { do{j--;} while(A[j] > x); do{i++;} while(A[i] < x); if(i < j) swap(A[i], A[j]); else return j; Print(A, 12); } } void Hoare_QuickSort(int *A, int p, int r) { if(p < r) { int q = Hoare_Partition(A, p, r); Hoare_QuickSort(A, p, q-1); Hoare_QuickSort(A, q+1, r); } } ``` ### 7-2 對快速排序算法的另一種分析 a) ``` 1 + 2 + …… + n n + 1 E[Xi] = -------------------- = ------- n 2 ``` b)后面幾題表示完全看不懂 ### 7-3 Stooge排序 ```c++ void Stooge_Sort(int *A, int i, int j) { if(A[i] > A[j]) swap(A[i], A[j]); if(i + 1 >= j) return; k = (j - i + 1) / 3; Stooge_Sort(A, i, j-k); Stooge_Sort(A, i+k, j); Stooge_Sort(A, i, j-k); } ``` 以下內容轉http://blog.csdn.net/zhanglei8893 a）對于數組A[i...j]，STOOGE-SORT算法將這個數組劃分成均等的3份，分別用A, B, C表示。第6-8步類似于冒泡排序的思想。它進行了兩趟：第一趟的第6-7步將最大的1/3部分交換到C 第二趟的第8步將除C外的最大的1/3部分交換到B 剩余的1/3位于A，這樣的話整個數組A[i...j]就有序了。 b）比較容易寫出STOOGE-SORT最壞情況下的運行時間的遞歸式 T(n) = 2T(2n/3)+Θ(1) 由主定律可以求得T(n)=n^2.71 c）各種排序算法在最壞情況下的運行時間分別為：插入排序、快速排序：Θ(n^2) 堆排序、合并排序：Θ(nlgn) 相比于經典的排序算法，STOOGE-SORT算法具有非常差的性能，這幾位終生教授只能說是浪得虛名了^_^ ### 7-4 快速排序中的堆棧深度 a) ```c++ void QuickSort2(int *A, int p, int r) { while(p < r) { int q = Partition(A, int p, r); QuickSort2(A, p, q-1); p = q + 1; } } ``` b) A = {1, 2, 3, 4, 5, 6} c) ```c++ void QuickSort3(int *A, int p, int r) { while(p < r) { int q = Partition(A, int p, r); if(r-q > q-p) { QuickSort3(A, p, q-1); p = q + 1; } else { QuickSort3(A, q+1, r); r = q - 1; } } } ``` ### 7-5 “三數取中”劃分 a)n個數任意取三個不同的數的取法共有C(3,n)種若要x=A'[i]，必須在A'[1..i-1]中取一個數，在A'[i+1..n]中取一個數取法共(i-1)*(n-i) ``` (i-1) * (n-i) 6 * (i-1) * (n-i) pi = --------------- = ------------------- C(3,n) n * (n-1) * (n-2) ``` b)在一般實現中，pi=1/n。 n->正無窮時，極限為0。在這種實現中，當i=(n+1)/2時， ``` 3(n-1) pi = ---------，當n->正無窮時，極限為0 2n(n-2) ``` c)遇到這種數學題就沒辦法了，哎，以前數學沒學好 d)不會求 [附自己寫的程序](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/src/chapter7/Exercise7_5.cpp) ### 7-6 對區間的模糊排序見[算法導論7-6對區間的模糊排序](http://blog.csdn.net/mishifangxiangdefeng/article/details/7681109)