第9章排序和順序統計學算法導論 · 《算法導論》答案

# 一、概念第i個順序統計量是該集合中第i小的元素。當n為奇數時，中位數是出現在i=(n+1)/2處的數。當n為偶數時，中位數分別出現在i=n/2和i=(n+1)/2處。在本文中，忽略n的奇偶性，中位數是指出現在i=(n+1)/2處的數。本文假設集合中的數互異。 # 二、代碼 ~~~ #include <iostream> using namespace std; //書中的程序 int length_A; void Print(int *A) { int i; for(i = 1; i <= length_A; i++) cout<<A[i]<<' '; cout<<endl; } /*******線性時間求最小值****************************/ int Minimun(int *A) { int Min = A[1], i; //依次查看集合中的每個元素 for(i = 2; i < length_A; i++) //記錄比較過程中最小的元素 if(Min > A[i]) Min = A[i]; return Min; } /*******通過3n/2次比較求最小值和最大值****************************/ void MinAndMax(int *A,int &Min, int &Max) { int i; //如果n是奇數 if(length_A % 2 == 1) { //將最大值和最小值設置為第一個元素 Min = A[1]; Max = A[1]; i = 2; } //如果n是偶數 else { //將前兩個元素作一次比較，以決定最大值懷最小值的初值 Min = min(A[1], A[2]); Max = A[1] + A[2] - Min; i = 3; } //成對地處理余下的元素 for(; i <= length_A; i=i+2) { //將一對輸入元素互相比較 int a = min(A[i], A[i+1]); int b = A[i] + A[i+1] - a; //把較小者與當前最小值比較 if(a < Min) Min = a; //把較大者與當前最大值比較 if(b > Max) Max = b; } } /********以期望線性時間作選擇********************/ //已經出現很多次了，不解釋 int Partition(int *A, int p, int r) { int x = A[r], i = p-1, j; for(j = p; j < r; j++) { if(A[j] <= x) { i++; swap(A[i], A[j]); } } swap(A[i+1], A[r]); return i+1; } int Randomized_Partition(int *A, int p, int r) { //隨機選擇數組中一個數作為主元 int i = rand() % (r-p+1) + p; swap(A[r], A[i]); //劃分 return Partition(A, p, r); } //i是從1開使計數的，不是從p開始 int Randomized_Select(int *A, int p, int r, int i) { if(p == r) return A[p]; //以某個元素為主元，把數組分為兩組，A[p..q-1] < A[q] < A[q+1..r]，返回主元在整個數組中的位置 int q = Randomized_Partition(A, p, r); //主元是整個數組中的第q個元素，是A[p..r]數組中的第k個元素 int k = q - p + 1; //所求的i中A[p..r]中的第i個元素 if(i == k)//正是所求的元素 return A[q]; else if(i < k)//所求元素<主元，則在A[p..q-1]中繼續尋找 return Randomized_Select(A, p, q-1, i); else//所求元素>主元，則在A[q+1..r]中繼續尋找 return Randomized_Select(A, q+1, r, i-k); } /*******最壞情況線性時間的選擇**************************/ int Select(int *A, int p, int r, int i); //對每一組從start到end進行插入排序，并返回中值 //插入排序很簡單，不解釋 int Insert(int *A, int start, int end, int k) { int i, j; for(i = 2; i <= end; i++) { int t = A[i]; for(j = i; j >= start; j--) { if(j == start) A[j] = t; else if(A[j-1] > t) A[j] = A[j-1]; else { A[j] = t; break; } } } return A[start+k-1]; } //根據文中的算法，找到中值的中值 int Find(int *A, int p, int r) { int i, j = 0; int start, end, len = r - p + 1; int *B = new int[len/5+1]; //每5個元素一組，長度為start到end，對每一組進行插入排序，并返回中值 for(i = 1; i <= len; i++) { if(i % 5 == 1) start = i+p-1; if(i % 5 == 0 || i == len) { j++; end = i+p-1; //對每一組從start到end進行插入排序，并返回中值,如果是最后一組，組中元素個數可能少于5 int ret = Insert(A, start, end, (end-start)/2+1); //把每一組的中值挑出來形成一個新的數組 B[j] = ret; } } //對這個數組以遞歸調用Select()的方式尋找中值 int ret = Select(B, 1, j, (j+1)/2); //delete []B; //很奇怪，這句話應該是沒問題的，但是怎么一運行到這句話就死機呢？ return ret; } //以f為主元的劃分 int Partition2(int *A, int p, int r, int f) { int i; //找到f的位置并讓它與A[r]交換 for(i = p; i < r; i++) { if(A[i] == f) { swap(A[i], A[r]); break; } } return Partition(A, p, r); } //尋找數組A[p..r]中的第i大的元素，i是從1開始計數，不是從p開始 int Select(int *A, int p, int r, int i) { //如果數組中只有一個元素，則直接返回 if(p == r) return A[p]; //根據文中的算法，找到中值的中值 int f = Find(A, p, r); //以這個中值為主元的劃分，返回中值在整個數組A[1..len]的位置 //因為主元是數組中的某個元素，劃分好是這樣的，A[p..q-1] <= f < A[q+1..r] int q = Partition2(A, p, r, f); //轉換為中值在在數組A[p..r]中的位置 int k = q - p + 1; //與所尋找的元素相比較 if(i == k) return A[q]; else if(i < k) return Select(A, p, q-1, i); else //如果主元是數組中的某個元素，后面一半要這樣寫 return Select(A, q+1, r, i-k); //但是如果主元不是數組中的個某個元素，后面一半要改成Select(A, q, r, i-k+1) } int main() { cin>>length_A; int *A = new int[length_A+1], i, cnt; //生成測試數據 for(i = 1; i <= length_A; i++) A[i] = rand() % 100; cin>>cnt; //顯示測試數據 Print(A); //輸出結果 if(cnt <= length_A) cout<<Select(A, 1, length_A, cnt)<<endl; return 0; } ~~~ # 三、習題 ### 9.1 最小值和最大值 9.1-1 見[算法導論 9.1-1 求第二小元素](http://blog.csdn.net/mishifangxiangdefeng/article/details/7983809) ### 9.2 以期望線性時間做選擇 ~~~ 9.2-3 RANDOMIZED-SELECT(A, p, r, i) 1 while true 2 if p = r 3 then return A[p] 4 q <- RANDIMIZED-PARTITION(A, p, r) 5 k <- q - p + 1 6 if i = k 7 then return A[q] 8 else if i < k 9 then q <- q-1 10 else 11 q <- q + 1 12 i <- i - k 9.2-4 A = {3, 2, 9, 0, 7, 5, 4, 8, 6, 1} ==> A = {3, 2, 0, 7, 5, 4, 8, 6, 1, 9} ==> A = {3, 2, 0, 7, 5, 4, 6, 1, 8, 9} ==> A = {3, 2, 0, 5, 4, 6, 1, 7, 8, 9} ==> A = {3, 2, 0, 5, 4, 1, 6, 7, 8, 9} ==> A = {3, 2, 0, 4, 1, 5, 6, 7, 8, 9} ==> A = {3, 2, 0, 1, 4, 5, 6, 7, 8, 9} ==> A = {2, 0, 1, 3, 4, 5, 6, 7, 8, 9} ==> A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ==> A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ==> A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ~~~ ### 9.3 最壞情況線性時間的選擇 9.3-3 先中SELECT選擇中值，再用這個中值進行劃分，代碼見[算法導論-9.3-3](http://blog.csdn.net/mishifangxiangdefeng/article/details/7687733) ~~~ QUICKSORT(A, p, r) 1 if p > r 2 then return 3 i <- (r-p+1) / 2 4 x <- SELECT(A, p, r, i) 5 q <- PARTITION(A, p, r, x) //以x為主元的劃分 6 QUICKSORT(A, p, q-1) 7 QUICKSORT(A, q+1, r) ~~~ 9.3-5 ~~~ SELECT(A, p, r, i) 1 if p = r 2 then return A[p] 3 x <- MEDIAN(A, p, r) 4 q <- PARTITION(A, p, r, x) //以x為主元的劃分 5 k <- q - p + 1 6 if i = k 7 then return A[q] 8 else if i < k 9 then return SELECT(A, p, q-1, i) 10 else return SELECT(A, q+1, r, i-k) ~~~ 9.3-6 令每個子集合的元素個數為t = n / k，A[j]是數組A中下標為j的元素，A(j)是數組是第j大的元素則所求的k分位數是指A(t)，A(2t)，A(3t)，……，A((k-1)t) 按順序依次求這k-1個數的運行時(k-1)*n 要使運行時間為O(nlgk)，改進方法是不要依次尋找這k-1個數，而是借用二分的方法來找。先找第k/2個分位數，再以這個分位數為主元把數組分為兩段，分別對這兩段來找分位數，這個時候找的范圍變小了，效率也就提高了見[算法導論-9.3-6](http://blog.csdn.net/mishifangxiangdefeng/article/details/7689102) 9.3-7 step1：求出數組的中位數的值O(n) step2：計算數組每個數與中位數差的絕對值，存于另一個數組B中O(n) step3：求出數組B中第k小的數ret O(n) step4：計算數組S中與ret差的絕對值小于ret的數并輸出O(n) 其中，step4也可以通過劃分的方法找出數組S中與ret差的絕對值小于ret的數代碼見[算法導論-9.3-7](http://blog.csdn.net/mishifangxiangdefeng/article/details/7689900) 9.3-8 遞歸求解該問題，解題規模不斷減半，最后剩下4個元素時，得到問題的解分別取兩個數組的中值minA和minB進行比較如果minA=minB，那么這個值就是結果否則，小的那個所在的數組去掉前面一半，大的那個去掉后面一半。（對于兩個數組的中值，共有n-1個元素，有n個元素比它大。但是對于min(minA,minB)，最多只有n-2個元素比它小，所以一定不是所求的結果，同理去掉大的一半）然后對剩余的兩個數組，用同的方法求它們的中值，直到兩個數組一共剩下4個元素代碼見[算法導論-9.3-8](http://blog.csdn.net/mishifangxiangdefeng/article/details/7690461) 9.3-9 這題其實挺簡單的，就是不一定能找到這個規律。為了簡化這道題，不考慮點的y坐標，假設所有的點都在一條與管道垂直的線上假如有兩個點AB，分別在管道l的上下，那么不管這條管道在什么位置（只要在AB之間），d[Al]+d[bl]=d[AB]。根據以上規律，把每兩個點分為一組，第i組中的點是（第i大的點，第i小的點），只要管道在每組的兩個點之間，就能保證長度總和最小。由以上推理得出答案：令所以x作為的中值為s(i)，如果點的個數是奇數，管道過s(i)點如果點的個數是偶數，管道位于點s(i)和s(i+1)之間（包括這兩點） # 四、思考題 ### 9-1 已排序的i個最大數 ~~~ a）合并排序和堆排序,O(nlgn) b）堆排序,O(n+ilgn) c）快速排序,O(n+ilgi) ~~~ ### 9-2 帶權中位數 b）使用最壞情況時間為O(nlgn)的排序算法對每個元素進行排序依次累加元素的權重，直到滿足題目中公式 c） step1：利用SELECT中尋找中值的中值的算法，找到主元 step2：用主元把數組分為三段，即A[1..q-1] < A[q] < A[q+1..r] step3：計算A[1..q-1]<0.5和A[1..q]>=0.5的權值和，是否滿足題目中的公式 step4：若滿足，A[q]就是所求的數 step5：若不滿足，就繼續遞歸使用本算法進行遞歸查找。偏大就找前半段，偏小就找后半段代碼見[算法導論-9-2-c-帶權中位數](http://blog.csdn.net/mishifangxiangdefeng/article/details/7690962) 郵局位置問題：關鍵是d)的結論 ### 9-3 小型順序統計量 a）待解決