【正文】 x首先與 10比較，由于 22比 10大，故下一步在右子樹中尋找； …… ；以此類推，直至 22。 定理 （ Page 6） 對(duì)于一個(gè)大小為 n的已排序數(shù)組，算法BinarySearch 執(zhí)行比較的最大次數(shù)為 : ?Log2n? +1 ? 容易看出，在最壞的情況下，第一個(gè)算法要檢測(cè)A的所有 n個(gè)分量才能判斷在 A中找不到等于 x的分量； ? 在第二個(gè)算法中，最壞的情況下最多只要測(cè) A中的 j+1(j=log2n)個(gè)分量，就判斷 x是否在 A中，第一個(gè)算法和第二個(gè)算法解決的是同一個(gè)問題，但在最壞的情況下（所給定的 x不在 A中），兩個(gè)算法所檢測(cè)的分量個(gè)數(shù)卻大不相同，前者要 n=2j個(gè)，后者只要 j+1個(gè)，可見第二個(gè)算法比第一個(gè)算法高效得多。 22 23 選擇排序法 ㈠ 選擇算法 假定有一個(gè)數(shù)組 A[1..n]， A[i..n]是它的一個(gè)子數(shù)組， 1≤i＜ n。 過程 Selection（參見 Page 8） 輸入： A[i..n] 輸出： A[i..n]，其中 A[i]為 A[i..n]中的最小的數(shù)。 算法 SelectionSort（參見 Page 8） 輸入：數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. for i←1 to n 1 2. Selection(i) 3. end for 25 26 2 1)n ( n1.. .2)(n1)(n ???????㈢ 選擇排序算法分析 這個(gè)算法執(zhí)行的元素比較次數(shù)為： (Page49) 可以看出元素的交換次數(shù)界于 0和 n1之間，由于每次交換需要 3次元素賦值，因此元素賦值次數(shù)界于 0和 3(n1)之間。 27 插入排序 ㈠ 插入算法 假定有一個(gè)數(shù)組 A[1..n]， A[1..i]是它的一個(gè)子數(shù)組（ 1＜ i≤n）。編寫一函數(shù)，作用為：將 x=A[i]插入到子數(shù)組 A[1..i] 中，使得 A[1..i]按升序排列。在掃描的每一步，元素都被移到序號(hào)更高的一個(gè)位置上，這種過程直到以下情況出現(xiàn)時(shí)終止： ①找到一個(gè)小于等于 x=A[i]的元素 A[j] ② 元素 A[1]已掃描過（顯然 j=0） 此時(shí)可將 x插入到 A[j+1] 。 算法 InsertionSort(參見 Page 89) 輸入：數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. for i←2 to n 2. Insertion(i) 3 end for 30 ㈢ 插入排序算法分析 執(zhí)行 InsertionSort，元素比較次數(shù)取決于輸入元素的順序。 ②當(dāng)元素已按降序排列，并且所有元素各不相同，比較次數(shù)為最大。 31 觀察結(jié)論 （ Page 9） 執(zhí)行算法 InsertionSort的元素比較次數(shù)在 n1到 n(n1)/2之間。 32 “選擇排序法”和“插入排序法”小結(jié) (1)選擇排序法（往后選擇） Seletion(i) 從 A[i..n]中選擇一個(gè)最小的數(shù)（ 1≤i≤n1），將其和 A[i]交換，顯然 A[i]≥A[i1]（當(dāng) i≥2時(shí)），故 A[1..i]有序。 (2)插入排序法（向前插入） Insertion(i) A[1..i1]已有序（ 2≤i≤n），將 A[i]中的元素插入到A[1..i1]中一個(gè)的合適位置，使得 A[1..i]有序。 33 合并二個(gè)已排序的表 ㈠ 算法描述 假定有一個(gè)數(shù)組 A[1..m]， p， q， r是它的三個(gè)索引，并有1≤p≤qr≤m，二個(gè)子數(shù)組 A[p..q]和 A[q+1..r]各自按升序排列，重新排列 A中元素的位置，使得子數(shù)組 A[p..r]按升序排列。然后更新指針，若 A[s]≤A[t]，則 s加 1，否則 t加 1； ③當(dāng) s=q+1，說明子數(shù)組 A[p..q]的全部元素已進(jìn)入 B，無需再比較，此時(shí)把子數(shù)組余下部分 A[t..r]添加到 B中； ④當(dāng) t=r+1，說明子數(shù)組 A[q+1..r]的全部元素已進(jìn)入 B，無需再比較，此時(shí)把子數(shù)組余下部分 A[s..q]添加到 B中； ⑤最后將 B[p..r]復(fù)制到 A[p..r]。 輸出：子數(shù)組 A[p..r]按升序排列。 11. end if 12. A[p..r]← B[p..r] //復(fù)制 35 2 3 16 7 11 13 45 57 q r=8 k=1 t=4 s=1 p A[p..r]=A[p..q]+A[q+1..r] ={2,3,16}+{7,11,13,45,57} B[p..r]={2,3,7,11,13,16,45,57} 36 ㈡ 算法分析 設(shè)有個(gè)數(shù)分別為 n1和 n2的二個(gè)子數(shù)組 n1+n2=n，如果子數(shù)組 A[p..q]中每個(gè)元素均小于另一個(gè)子數(shù)組 A[q+1,r]中的所有元素，例，要合并下面二個(gè)子數(shù)組： 2 3 6 7 11 13 45 57 該算法只需執(zhí)行 3次比較，即 n1次比較。例如要合并下面二個(gè)子數(shù)組： 2 3 66 7 11 13 45 57 就需要 7次比較。 37 觀察結(jié)論 （ Page 7） 執(zhí)行算法 Merge，將個(gè)數(shù)分別為 n1和 n2的非空數(shù)組合并成一個(gè)為 n= n1+n2的排序數(shù)組。特例，如果二個(gè)數(shù)組大小為 ?n/2?和 ?n/2? ，需要比較的最大次數(shù)在 ?n/2?和 n1之間。 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成正比，從這個(gè)意義上來說二種算法的效率都是比較低的，考慮下面的排序方法： 39 ㈡ 自底向上合并排序算法 設(shè) A[1..n]為需排序的 n個(gè)元素的數(shù)組 ①第 1次迭代 生成個(gè)數(shù)為 2（ =21）的排序序列，該序列共有 = 個(gè)。 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次迭代 生成個(gè)數(shù)為 4（ =22）的排序序列，共有 = 個(gè)。如果剩余 3個(gè)，則將 2個(gè)元素（已排序）和另外 1個(gè)元素合并成一個(gè) 3元素的排序序列。 可能剩余的元素個(gè)數(shù) r，其大小在 1至 2j1之間 (j=3,r=17)。 ?若 2j1＜ r＜ 2j (j=3,r=57)，則將 2j1個(gè)元素（局部已有序）和另外 r 2j1個(gè)元素（局部已有序）合并成個(gè)數(shù)為 r的排序序列。 k1＜ log2n≤k。 ? s為被合并的子序列長度，初始時(shí)為 1，每循環(huán)一次乘以 2； ? t為 s的二倍，即二個(gè)子序列合并后的長度，可省略 (見下頁 )； ? 當(dāng) n不是 t的整數(shù)倍，出內(nèi)層循環(huán)后執(zhí)行第 8步。 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 ㈢ 示例 當(dāng) n不是 2的整數(shù)冪時(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時(shí)， i+t=12≤11不成立，出循環(huán)。 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時(shí)， i+t≤11不成立，出循環(huán)。 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時(shí)， i+t≤11不成立，出循環(huán)。 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時(shí)， i+t≤11不成立，出循環(huá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í)行。在執(zhí)行內(nèi)部循環(huán)后，由于 n為 2的冪，故第 8步永遠(yuǎn)不會(huì)執(zhí)行。 n個(gè)元素被劃分為 n/2個(gè)段 （段長 =2），段內(nèi)有序。根據(jù)觀察結(jié)論 （ Page 7），每對(duì)合并需要的比較次數(shù)，最少為 2，最多為 3。根據(jù)觀察結(jié)論 （ Page 7），每對(duì)合并需要的比較次數(shù)，最少是 4，最多7。根據(jù) Page 7觀察結(jié)論 （ Page 7）