第8章線性時間排序 · 《算法導論》答案

# 一、概念 ### 1.比較排序比較排序是指通過輸入元素間的比較來確定各元素次序的排序算法。任何比較排序在最壞情況下都要用O(nlgn)次比較來進行排序合并排序和堆排序是漸近最優的 ### 2.非比較排序非比較排序指使用一些非比較的操作來確定排序順序的排序算法對于非比較排序，下界O(nlgn)不適用計數排序是穩定排序，若n個數據的取值范圍是[0..k]，則運行時間為O(n+k)，運行空間是O(n+k) 基數排序也是穩定排序，需要另一個穩定排序作為基礎，若n個d位數，每一位有k種取值可能，所用的穩定排序運行時間為O(n+k)，則基數排序的時間是O(d(n+k)) 桶排序也是穩定排序，當輸入數據符合均勻分布時，桶排序可以以線性時間運行。所設所有元素均勻分布在區間[0,1)上，把區間[0,1)劃分成n個相同大小的子區間（桶），對各個桶中的數進行排序，把依次把各桶中的元素列出來。 # 二、代碼 ~~~ #include <iostream> #include <cmath> using namespace std; int length_A, digit; void Print(int *A, int start, int end) { int i; for(i = start; i <= end; i++) { if(i == start)cout<<'{'; else cout<<' '; cout<<A[i]; } cout<<'}'<<endl; } //計數排序 void Counting_Sort(int *A, int *B, int k) { int i, j; //將C數組初始化為0，用于計數 int *C = new int[k+1]; for(i = 0; i <= k; i++) C[i] = 0; //C[j]表示數字j在數組A中出現的次數 for(j = 1; j <= length_A; j++) C[A[j]]++; //C[i]表示所以<=i的數字出現過的次數 for(i = 1; i <= k; i++) C[i] = C[i] + C[i-1]; //初始化B為0，B用于輸出排序結果 for(i = 1; i <= length_A; i++) B[i] = 0; for(j = length_A; j >= 1; j--) { //如果<=A[j]的數字的個數是x,那么排序后A[j]應該出現在第x個位置，即B[x]=A[j] B[C[A[j]]] = A[j]; C[A[j]]--; } delete C; } //基數排序調用的穩定排序 void Stable_Sort(int *A, int *B, int k, int d) { int i, j; //將C數組初始化為0，用于計數 int *C = new int[k+1]; for(i = 0; i <= k; i++) C[i] = 0; int *D = new int[length_A+1]; for(j = 1; j <= length_A; j++) { //D[j]表示第[j]個元素的第i位數字 D[j] = A[j] % (int)pow(10.0, d) / (int)pow(10.0, d-1); //C[j]表示數字D[j]在數組A中出現的次數 C[D[j]]++; } //C[i]表示所以<=i的數字出現過的次數 for(i = 1; i <= k; i++) C[i] = C[i] + C[i-1]; //初始化B為0，B用于輸出排序結果 for(i = 1; i <= length_A; i++) B[i] = 0; for(j = length_A; j >= 1; j--) { //如果<=D[j]的數字的個數是x,那么排序后A[j]應該出現在第x個位置，即B[x]=A[j] B[C[D[j]]] = A[j]; C[D[j]]--; } delete []C; delete []D; } //基數排序 void Radix_Sort(int *A, int *B) { int i, j; //依次對每一位進行排序，從低位到高位 for(i = 1; i <= digit; i++) { Stable_Sort(A, B, 9, i); //輸入的是A，輸出的是B，再次排序時要把輸出數據放入輸出數據中 for(j = 1; j <= length_A; j++) A[j] = B[j]; } } int main() { cin>>length_A>>digit; int *A = new int[length_A+1]; int *B = new int[length_A+1]; int i; //隨機產生length_A個digit位的數據 for(i = 1; i <= length_A; i++) { A[i] = 0; while(A[i] < (int)pow(10.0, digit-1)) A[i] = rand() % (int)pow(10.0, digit); } Print(A, 1, length_A); // Counting_Sort(A, B, 9); Radix_Sort(A, B); Print(A, 1, length_A); delete []A; delete []B; return 0; } ~~~ # 三、練習 ### 8.1 排序算法時間的下界 ~~~ 8.1-1 <span style="line-height: 20px; ">n-1，因為一個有序數組的排序中最少會進行n-1次比較</span> 8.1-2 數學題目不要看我 8.1-3 幸好有答案，不然題目的意思都看不懂。先解釋一下題目的意思，高手跳過。對于一個組包含n個元素的數據，可以有n!種不同的排列，也就是有n!種不同的輸入。對于一個排序算法，可以用一個決策樹來表示。對于任意一種輸入排列，從樹頂出發，根據該內結點的提示作對應的比較和調整，并決定進入其左子樹還是右子樹。當這個排列成為一個有序序列時到達葉子結點。這個葉結點就是這個輸入排列對應的葉結點。從根結點到葉結點的長度就是這個排列的比較次數。具有線性時間的輸入是指n!種輸入排列中滿足以下條件的排列：排列的運行時間小于或等于O(n) 假設對于一組包含n個元素的數據，有n!種不同的輸入排列，其中具有線性時間的輸入排列有m種，求k = m/(n!) 若k<=1/2，那么所證明的命題成立。后面一問是指k和1/n、1/(2^n)的比較證明：這m種輸入排列分別對應決策樹中的m個葉結點。一棵高度為h的樹最多有2^h個葉結點。 2^h >= m =====> h >= lg(m) 若要一棵決策樹包含m個葉結點，這棵決策樹的高度最少為lg(m) 根據《算法導論》P98中定理8.1的公式，h>=O(nlgn) 只需要證明lg(m) <= O(nlgn)，那么k就是可以取到的值。分別令k等于1/2、1/n、1/(2^n),代入m = k * (n!)得：計算結果略，這幾個值都不滿足 8.1-4 不能簡單地將子序列的下界合起來，這樣做不準確。因為有可能存在一種比“獨立解決各個子序列的排序”更快的算法。這種計算比較次數的一般思路是： (1)統計有多少種不同的輸入排列 (2)每一種輸入排列對應決策樹的一個葉子結點。 (3)根據葉結點的數量與樹的高度的關系，計算決策樹的高度 (4)從樹根到葉結點的長度就是這個葉結點對應的輸入排列的比較次數對于這道題，可以這樣計算： (1)每個子序列有k個元素，因此有k!種不同的輸入排列。共有n/k個子序列，因此共有(k!)^(n/k)種輸入排列 (2)決策樹至少有(k!)^(n/k)個葉子 (3)一棵高度為h的決策樹，最多有2^h個葉子結點 2^h >= (k!)^(n/k) =====> h >= (n/2)lg(k/2) (4)對于任意一樹決策樹，至少有一條葉子路徑長度超過(n/2)lg(k/2)，因此比較次數下界是O(nlgk) ~~~ ### 8.2 計數排序 ~~~ 8.2-1因為假設待排序數據的范圍中[0,k]，所以B被初始化為-1 A = {6 0 2 0 1 3 4 6 1 3 2} ==> C = {2 2 2 2 1 0 2} ==> C = {2 4 6 8 9 9 11} ==> B = {-1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1} C = {2 4 5 8 9 9 11} ==> B = {-1 -1 -1 -1 -1 2 -1 3 -1 0 -1 -1} C = {2 4 5 7 9 9 11} ==> B = {-1 -1 -1 1 -1 2 -1 3 -1 -1 -1} C = {2 3 5 7 9 9 11} ==> B = {-1 -1 -1 1 -1 2 -1 3 -1 -1 6} C = {2 3 5 7 9 9 10} ==> B = {-1 -1 -1 1 -1 2 -1 3 4 -1 6} C = {2 3 5 7 8 9 10} ==> B = {-1 -1 -1 1 -1 2 3 3 4 -1 6} C = {2 3 5 6 8 9 10} ==> B = {-1 -1 1 1 -1 2 3 3 4 -1 6} C = {2 2 5 6 8 9 10} ==> B = {-1 0 1 1 -1 2 3 3 4 -1 6} C = {1 2 5 6 8 9 10} ==> B = {-1 0 1 1 2 2 3 3 4 -1 6} C = {1 2 4 6 8 9 10} ==> B = {0 0 1 1 2 2 3 3 4 -1 6} C = {0 2 4 6 8 9 10} ==> B = {0 0 1 1 2 2 3 3 4 6 6} C = {0 2 4 6 8 9 9} 8.2-2 輔助數組C[j]記錄的是小于或等于i的元素的個數。若幾個元素的大小相等，則把這些元素依次從后往前填入排序數組中。因為處理元素的順序是從后往前的(L9)，所以晚出現的元素會填到后面。因此是穩定排序 8.2-3 不穩定 8.2-4 COUNTING-SORT(A, B, k)中步驟L1-L4求出C，ans(a, b) = C[b] - C[a-1], C[-1]=0 ~~~ ### 8.3 基數排序 8.3-1 ~~~ A = {COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX} ==> A = {SEA, TEA, MOB, TAB, DOG, RUG, DIG, BIG, BAR, EAR, TAR, COW, ROW, NOW, BOX, FOX} ==> A = {TAB, BAR, EAR, TAR, SEA, TEA, DIG, BIG, MOB, DOG, COW, ROW, NOW, BOX, FOX, RUB} ==> A = {BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, TAB, TAR, TEA, SEA, RUB} ~~~ 8.3-2 穩定排序有：插入排序，合并排序方法：為每一個元素加入一個最初位置的屬性，但兩個元素的value一樣大時，比較position，這樣不會有相同的兩個元素額外空間：O(4n) 8.3-3 (1)當d=1時，元素只有一位，對這一位做排序就相當于對整個數組做排序了。 (2)證明當1到d-1位排序是正確的時，對d位的排序也是正確的。 (3)對于數組中的任意兩個數a和b，假設它們的第d位分別是ad和bd 若ad<bd，則a會排到b的前面若ad>bd，則a會排到b的后面若ad=bd，則a和b的相對位置不變，因為是穩定排序，這一點可以保證。 8.3-4 把整數轉換為n進制再排序，見[算法導論8.3-4](http://blog.csdn.net/mishifangxiangdefeng/article/details/7685839) 8.3-5 最壞情況下需要d遍 ### 8.4 桶排序 ~~~ 8.4-1 A = ｛0.79， 0.13， 0.16， 0.64， 0.39， 0.20， 0.89， 0.53， 0.71， 0.42｝ ==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.79， 0.71， 0.89｝ ==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.71， 0.79， 0.89｝ 8.4-2 最壞情況是O(n^2) 修改：使用最壞情況下時間為O(nlgn)的算法來處理桶的插入操作 8.4-3 E(X^2)=1/4 * 0 + 1/2 * 1 + 1/4 * 4 = 3/2 E^2(X)=[1/4 * 0 + 1/2 * 1 + 1/4 * 2]^2 = 1^2 = 1 8.4-4 假設分為n個桶 BUCKET-SORT(A) 1 n <- length[A] 2 for i <- 1 to n 3 do insert A[i] to list B[n*(A[i].x^2 + A[i].y^2)] 4 for i <- 0 to n-1 5 do sort list B[i] with insertion sort 6 concatenate the lists B[0], B[1], ……,B[n-1] together in order 8.4-5 ~~~ 不會，網上找了份答案，不懂 X合適分布P，不必然是均勻分布，且不知局限。但P(x)值屬于[0,1]，且對于X嚴格單調遞增，排序P(x)即排序X。將P(x)均勻分為n個項目組，因為X隨機拔取，所以落入每個局限的概率雷同。若是(i-1)/n <= p(xi) < i/n，則將它放入第i個桶中。 [http://www.mysjtu.com/page/M0/S696/696126.html](http://www.mysjtu.com/page/M0/S696/696126.html) # 四、思考題 ### 8-1 比較排序的平均情況下界 ~~~ a)n個不同的元素對應n!個不同的輸入，因此只有這n!個輸入所對應的葉結點是有概率的，其余概率均為0。由于這n!種輸入的出現是等概率的，每一種的都是1/n1，因此其對應的葉結點的概率也是1/n! b)設T(n)是一個葉子結點n的在決策樹T上的深度，RT(n)、LT(n)分別表示n在T的右、左子樹上的深度。那么T(n)=RT(n)+1或T(n)=LT(n)+1 因此D(T)=D(RT)+D(LT)+k c)后面這幾題，以我有限的智商和數學能力理解不了，也看不懂網上的答案，不寫了 ~~~ ### 8-2 以線性時間原地轉換排序 ~~~ a)計數排序 b)快速排序 c)穩定排序 d)基數排序要求所使用的排序方法是滿足的（條件2），如果要在O(bn)時間內完成，所使用算法的時間應該是O(n)（條件1），所以只有a可以 e)不穩定 COUNTING-SORT(A, k) 1 for i <- 0 to k 2 do C[i] <- 0 3 for j <-1 to length[A] 4 C[A[j]] <- C[A[j]] + 1 5 cnt <- 1 6 for i <- 1 to k 7 while C[i] > 0 8 A[cnt] <- i 9 C[i] <- C[j] - 1 10 cnt <- cnt + 1 ~~~ ### 8-3 排序不同長的數據項見[算法導論-8-3-排序不同長度的數據項](http://blog.csdn.net/mishifangxiangdefeng/article/details/7686099) ~~~ a)先用計數排序算法法按數字位數排序O(n)，再用基數排序的方法分別對每個桶中的元素排序O(n) b)遞歸使用計數排序，先依據第一個字母進行排序，首字相同的放在同一組，再對每一組分別使用計數排序的方法比較第二個字母見到有人用字典樹，也是可以的 ~~~ ### 8-4 水壺 ~~~ a)最原始的比較方法，所有的紅水壺與所有的藍水壺依次比較 c)算法類似于快排，由于不是同種顏色的水壺之間比較，所以采用交叉比較 step1：從紅色水壺中隨機選擇一個 step2：以紅色水壺為主元對藍色水壺進行劃分 step3：劃分的結果是兩個數組，并得到與紅色水壺相同大小的藍色水壺 step4：以這個藍色水壺為主元，對紅色水壺進行劃分 step5：用step1到step4的過程不斷迭代 ~~~ ### 8-5 平均排序見[算法導論6.5-8堆排序-K路合并](http://blog.csdn.net/mishifangxiangdefeng/article/details/7668486) ~~~ a)1排序是完全排序 b)1，3，2，4，5，7，6，8，9，10 c)分工展開化簡即可 d) step1：分別把1, 1+k, 1+2k, 1+3k,……;2, 2+k, 2+2k, 2+3k,……；……當作是單獨的集合 step2：對每個集合進行排序時間為O(nlg(n/k)) e) step1：同d)step1 step2：用堆排序進行k路合并 ~~~ ### 8-6 合并已排序列表的下界 ~~~ a)2n個數，隨機選n個數，可選的方法有C(2n,n)種 b)2^h >= C(2n,n) =====> h >= lg((2n)!) - 2lg(n!) =====> h >= 2nlg2n - 2nlgn =====> h >= 2nlg2 只能推到這了，最后怎么算，還希望高手指點 c)d)看上去很顯然的事情，不知道怎么證 ~~~