【文章內(nèi)容簡介】 n2的排序數(shù)組，元素的賦值次數(shù)恰好是 2n。 38 2 4 5 9 9 4 5 2 1 7 4 6 4 9 2 5 1 7 4 6 1 4 6 7 1 2 4 4 5 6 7 9 自底向上合并排序 ㈠ 引入 插入和選擇排序法的最大比較次數(shù)都與 n2成正比，從這個意義上來說二種算法的效率都是比較低的，考慮下面的排序方法： 39 ㈡ 自底向上合并排序算法 設 A[1..n]為需排序的 n個元素的數(shù)組 ①第 1次迭代 生成個數(shù)為 2（ =21）的排序序列，該序列共有 = 個。若剩余 1個元素，則讓它進入下一輪合并。 2n12n9 4 5 2 1 7 4 6 4 9 2 5 1 7 4 6 9 4 5 2 1 7 4 4 9 2 5 1 7 4 40 ② 第 2次迭代 生成個數(shù)為 4（ =22）的排序序列，共有 = 個。若剩余 1或 2個，則讓它進入下一輪合并。如果剩余 3個，則將 2個元素（已排序）和另外 1個元素合并成一個 3元素的排序序列。 4n22n2 4 5 9 4 9 2 5 1 7 4 6 1 4 6 7 2 4 5 9 4 9 2 5 1 7 4 1 4 7 41 剩余元素為 7個 ③ 第 j次迭代（假設 j=3） 生成元素個數(shù)為 2j個的排序序列，該序列共有 個。 可能剩余的元素個數(shù) r，其大小在 1至 2j1之間 (j=3,r=17)。 ?若 1≤r≤ 2j1(j=3,r=14)，則讓它們進入下一次合并（局部已有序）。 ?若 2j1＜ r＜ 2j (j=3,r=57)，則將 2j1個元素（局部已有序）和另外 r 2j1個元素（局部已有序）合并成個數(shù)為 r的排序序列。 jn22 4 5 9 1 4 6 7 1 2 4 4 5 6 7 9 2 4 5 9 1 4 7 1 2 4 4 5 7 9 ④ 總的迭代次數(shù) k的值范圍為： 2k1＜ n≤ 2k 。 k1＜ log2n≤k。 42 算法 BottomUpSort（ Page 10） 輸入： n個元素的數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. t←1 2. while tn 3. s←t : t←2s : i←0 //i表示要處理數(shù)據(jù)的起始地址 (簡稱位移 ) 4. while i+t≤n 5. Merge(A,i+1,i+s,i+t) //Merge(A,p,q,r) 6. i←i+t //i表示要處理數(shù)據(jù)的起始地址 (簡稱位移 ) 7. end while 8. if i+sn then Merge(A,i+1,i+s,n) 9. end while //起始地址 +被合并前子序列長度＜ n，則合并。 ? s為被合并的子序列長度，初始時為 1，每循環(huán)一次乘以 2； ? t為 s的二倍，即二個子序列合并后的長度，可省略 (見下頁 )； ? 當 n不是 t的整數(shù)倍，出內(nèi)層循環(huán)后執(zhí)行第 8步。如果剩余元素數(shù)目大于 s，就要將最后一個長度為 s的子序列和剩余元素進行一次合并排序，此時二個子序列合并后的長度小于 t=2s。 43 6 10 9 5 3 11 4 8 1 2 7 6 10 5 9 3 11 4 8 1 2 7 5 6 9 10 3 4 8 11 1 2 7 3 4 5 6 8 9 10 11 1 2 7 1 2 3 4 5 6 7 8 9 10 11 ㈢ 示例 當 n不是 2的整數(shù)冪時，自底向上合并排序的過程如下所示： 44 第 1次迭代： t=1＜ n=11成立 s=1,t=2 i值的范圍： 0,2,4,8,10 i=0 MERGE(A,1,1,2) i=2 MERGE(A,3,3,4) i=4 MERGE(A,5,5,6) i=6 MERGE(A,7,7,8) i=8 MERGE(A,9,9,10) i=10時， i+t=12≤11不成立，出循環(huán)。 出循環(huán)后， i+s=10+1=11＜ n=11不成立，因此不再合并，最后一個序列長度為 1（或稱剩下的元素個數(shù)）。 MERGE(A,i+1,i+s,i+t) s表示被合并序列的長度（即合并前） t表示合并后序列的長度（初值為 1） i表示位移 6 10 9 5 3 11 4 8 1 2 7 6 10 5 9 3 11 4 8 1 2 7 1 2 3 4 5 6 7 8 9 10 11 45 第 2次迭代： t=2＜ n=11成立 s=2,t=4 i值的范圍： 0,4,8 i=0 MERGE(A,1,2,4) i=4 MERGE(A,5,6,8) i=8時， i+t≤11不成立，出循環(huán)。 出循環(huán)后， i+s=8+2＜ n=11成立，執(zhí)行 MERGE(A,9,10,n)，最后一個序列長度為 3。 MERGE(A,i+1,i+s,i+t) s表示被合并序列的長度（即合并前） t表示合并后序列的長度（初值為 1） i表示位移 6 10 5 9 3 11 4 8 1 2 7 5 6 9 10 3 4 8 11 1 2 7 1 2 3 4 5 6 7 8 9 10 11 46 第 3次迭代： t=4＜ n=11成立 s=4,t=8 i值的范圍： 0,8 i=0 MERGE(A,1,4,8) i=8時， i+t≤11不成立，出循環(huán)。 出循環(huán)后， i+s=8+4＜ n=11不成立，因此不再合并，最后一個序列長度為 3。 MERGE(A,i+1,i+s,i+t) s表示被合并序列的長度（即合并前） t表示合并后序列的長度（初值為 1） i表示位移 5 6 9 10 3 4 8 11 1 2 7 3 4 5 6 8 9 10 11 1 2 7 1 2 3 4 5 6 7 8 9 10 11 47 第 4次迭代： t=8＜ n=11成立 s=8,t=16 i值的范圍： 0 i=0時， i+t≤11不成立，出循環(huán)。 出循環(huán)后， i+s=0+8＜ n=11成立，執(zhí)行 MERGE(A,1,8,n)。 MERGE(A,i+1,i+s,i+t) s表示被合并序列的長度（即合并前） t表示合并后序列的長度（初值為 1） i表示位移 3 4 5 6 8 9 10 11 1 2 7 1 2 3 4 5 6 7 8 9 10 11 第 5次迭代： t=16＜ n=11不成立，程序終止執(zhí)行。 1 2 3 4 5 6 7 8 9 10 11 48 ㈣ 自底向上合并排序算法分析 假設數(shù)組元素個數(shù) n為 2的冪（ n=2k=2log n），外部循環(huán)次數(shù)為 k=log2n。在執(zhí)行內(nèi)部循環(huán)后，由于 n為 2的冪，故第 8步永遠不會執(zhí)行。 ①在第 1次迭代中，共執(zhí)行了 n/2 次比較。 n個元素被劃分為 n/2個段 （段長 =2），段內(nèi)有序。 ②在第 2次迭代中， n/2個段（段長 =2）元素序列被合并成 n/4個段（段長 =4），段內(nèi)有序。根據(jù)觀察結論 （ Page 7），每對合并需要的比較次數(shù)，最少為 2，最多為 3。 ③在第 3次迭代中， n/4個段（段長 =4）元素序列被合并成 n/8個段（段長 =8），段內(nèi)有序。根據(jù)觀察結論 （ Page 7），每對合并需要的比較次數(shù)，最少是 4，最多7。 49 最少比較次數(shù)（ k=log2n） ④ 在第 j次迭代中， 個段（段長 =2j1）元素序列被合并成 個段（段長 =2j），段內(nèi)有序。根據(jù) Page 7觀察結論 （ Page 7），每對合并需要的比較次數(shù)，最少是 2j1，最多為 2j1 。 12?jnjn250 最多比較次數(shù) ( k=log2n) ))211(( kkn ???)211( knnk ???knnnk2???1l o g 2 ??? nnn? ? ?????????? ??? kjjkjjjnnn11 2122????kjjnkn1 2151 觀察結論 （ Page 11) 用算法 BottomUpSort對 n個元素進行排序，當 n為 2的整數(shù)冪時，比較次數(shù)在(nlog2n)/2 到 nlog2nn+1 之間。執(zhí)行該算法的元素賦值次數(shù)為 2nlog2n。 52 時間復雜性 在計算復雜性領域中，主要是研究一個算法所需要的時間和空間。即當給出合法的輸入時，為了得到輸出，該算法執(zhí)行時所需要的時間和空間，其中時間尤為重要。 執(zhí)行算法 BottomUpSort的最大比較次數(shù) nlog2nn+1 執(zhí)行算法 SelectionSort的最大比較次數(shù) n(n1)/2 假設一次比較所需的時間為 106秒，當數(shù)據(jù)個數(shù) n分別為 27 =128 和 220 =1048576時，二個算法執(zhí)行所耗費的時間上限如下表所示： n SelectionSort BottomUpSort 27 106*128(1281)/2 ≈ 106*(128*7128+1) ≈ 220 106* 220 *(2201)/2≈ 106*(220*20 220+1) ≈ 20秒 53 ㈠ 概述 稱“一個算法 A對于輸入 x要用 y秒來運行”是沒有意義的，也是沒有必要的。因為影響一個算法的實際運行時間與諸多因素有關（例機器性能、語言選擇、編譯程序優(yōu)劣、程序員素質(zhì)等），甚至無需計算出算法運行時間的近似數(shù)。理由如下： ①算法分析通常是將解決同一問題的各種算法之間進行相互比較，執(zhí)行時間是相對的，而不是絕對的。 ②算法可以用各種語言來表示，甚至使用人類語言。 ③算法應獨立于機器，無論科技如何進步，對算法運行時間的評估始終成立。 ④算法分析不拘泥小規(guī)模數(shù)據(jù)的輸入，主要關心在大的輸入實例時，算法運行狀況。 例某一算法運行時間為 2n3 ，當 n變得很大時，常數(shù) 2將不起作用。觀察函數(shù) n2log2n+10n2+n 中的低階項 10n2和 n ，當 n值越大，10n2+n對函