【正文】 際元素比較最大次數(shù)應為循環(huán)（迭代）次數(shù)的 2倍，即 2( ?Log2n?+1)。 x首先與 10比較，由于 22比 10大，故下一步在右子樹中尋找； …… ；以此類推，直至 22。由于決策樹的高度為 ?Log2n? ，所以二分搜索法的最大比較次數(shù)為 ?Log2n? +1。 定理 （ Page 6） 對于一個大小為 n的已排序數(shù)組，算法BinarySearch 執(zhí)行比較的最大次數(shù)為 : ?Log2n? +1 ? 容易看出，在最壞的情況下，第一個算法要檢測A的所有 n個分量才能判斷在 A中找不到等于 x的分量； ? 在第二個算法中，最壞的情況下最多只要測 A中的 j+1(j=log2n)個分量，就判斷 x是否在 A中，第一個算法和第二個算法解決的是同一個問題，但在最壞的情況下（所給定的 x不在 A中），兩個算法所檢測的分量個數(shù)卻大不相同，前者要 n=2j個，后者只要 j+1個，可見第二個算法比第一個算法高效得多。 ? 因此，解決同一個問題，算法不同，計算的工作量也不同，所需的計算時間隨之不同，即算法的時間復雜性不同。 22 23 選擇排序法 ㈠ 選擇算法 假定有一個數(shù)組 A[1..n]， A[i..n]是它的一個子數(shù)組， 1≤i＜ n。編寫一函數(shù)，作用為：從 A[i..n] 中選擇一個最小的數(shù) A[k]（ i＜ k≤n） ，將 A[i]和 A[k]互換（若 k＝ i，無需交換）。 過程 Selection（參見 Page 8） 輸入： A[i..n] 輸出： A[i..n]，其中 A[i]為 A[i..n]中的最小的數(shù)。 0. procedure Selection(i) 1. k←i 2. for j←i+1 to n 3. if A[j]A[k] then k←j 4. end for 5. if k≠i then 交換 A[i]和 A[k] 6. end procedure 24 ㈡ 選擇排序算法 設 A[1..n]為 n個元素的數(shù)組，選擇排序算法如下： ①首先在 n個元素中找到最小元素，將其存放在 A[1]中； ②然后在剩下的 n1個元素中找到最小元素，將其存放在A[2]中； ③重復上述過程，直至在二個元素 A[n1]和 A[n]中找到較小元素，將其存放在 A[n1]中。 算法 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 ???????㈢ 選擇排序算法分析 這個算法執(zhí)行的元素比較次數(shù)為： (Page49) 可以看出元素的交換次數(shù)界于 0和 n1之間，由于每次交換需要 3次元素賦值，因此元素賦值次數(shù)界于 0和 3(n1)之間。 觀察結論 (Page 8) 執(zhí)行算法 SelectionSort所需的元素比較次數(shù)為 n(n1)/2，元素的賦值次數(shù)界于 0與 3(n1)之間。 27 插入排序 ㈠ 插入算法 假定有一個數(shù)組 A[1..n]， A[1..i]是它的一個子數(shù)組（ 1＜ i≤n）。 A[1..i1]已按升序排列。編寫一函數(shù)，作用為：將 x=A[i]插入到子數(shù)組 A[1..i] 中，使得 A[1..i]按升序排列。 依次掃描序號從 j=i1到 j=1的元素，將 x和 A[j]比較。在掃描的每一步，元素都被移到序號更高的一個位置上，這種過程直到以下情況出現(xiàn)時終止： ①找到一個小于等于 x=A[i]的元素 A[j] ② 元素 A[1]已掃描過（顯然 j=0） 此時可將 x插入到 A[j+1] 。 28 過程 Insertion（參見 Page 89） 輸入： A[1..i1]已按升序排列 輸出： A[1..i] 按升序排列 0. procedure Insertion(i) 1. x←A [i] 2. j←i 1 3. while (j0) and (A[j]x) 4. A[j+1]←A[j] 5. j←j 1 6. end while 7. A[j+1]←x 8. end procedure 29 ㈡ 插入排序算法 設 A[1..n]為 n個元素的數(shù)組，插入排序算法描述如下： ①從子數(shù)組 A[1]開始，單個數(shù)可認為有序； ②接下來，將 A[2]插入到 A[1]的前面或后面，使得A[1..2]有序； ③然后，再將 A[3]插入到 A[1..2]中，使得 A[1..3]有序； ④直到 A[n]插入到 A[1..n1]，使得 A[1..n]有序。 算法 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ù)取決于輸入元素的順序。 ①當元素已按升序排列時，元素比較次數(shù)最小，僅為 n1，每個元素 A[i]（ 2≤i≤n）只和 A[i1]比較。 ②當元素已按降序排列，并且所有元素各不相同，比較次數(shù)為最大。如下所示： 21)n( n1)(n...21 ????? 因為每個元素 A[i] (2≤i≤n)都和子序列 A[1..i1]中的每個元素比較，這一結果與算法 SelectionSort相一致。 31 觀察結論 （ Page 9） 執(zhí)行算法 InsertionSort的元素比較次數(shù)在 n1到 n(n1)/2之間。 元素賦值次數(shù)等于元素比較次數(shù)加上 n1，即 2(n1)至 n(n1)/2+(n1)之間。 32 “選擇排序法”和“插入排序法”小結 (1)選擇排序法（往后選擇） Seletion(i) 從 A[i..n]中選擇一個最小的數(shù)（ 1≤i≤n1），將其和 A[i]交換，顯然 A[i]≥A[i1]（當 i≥2時），故 A[1..i]有序。然后 i增 1，排序過程直至 i=n1結束。 (2)插入排序法（向前插入） Insertion(i) A[1..i1]已有序（ 2≤i≤n），將 A[i]中的元素插入到A[1..i1]中一個的合適位置，使得 A[1..i]有序。然后 i增 1，排序過程直至 i=n結束。 33 合并二個已排序的表 ㈠ 算法描述 假定有一個數(shù)組 A[1..m]， p， q， r是它的三個索引，并有1≤p≤qr≤m，二個子數(shù)組 A[p..q]和 A[q+1..r]各自按升序排列，重新排列 A中元素的位置，使得子數(shù)組 A[p..r]按升序排列。 ①使用二個指針 s和 t，初始化時 s=p、 t=q+1， s和 t各自指向 A[p]和 A[q+1]，空數(shù)組 B[p..r]用作暫存器； ②每一次比較元素 A[s]和 A[t]，將小的元素添加到 B中。然后更新指針，若 A[s]≤A[t]，則 s加 1，否則 t加 1； ③當 s=q+1，說明子數(shù)組 A[p..q]的全部元素已進入 B，無需再比較，此時把子數(shù)組余下部分 A[t..r]添加到 B中； ④當 t=r+1，說明子數(shù)組 A[q+1..r]的全部元素已進入 B，無需再比較，此時把子數(shù)組余下部分 A[s..q]添加到 B中； ⑤最后將 B[p..r]復制到 A[p..r]。 34 過程 Merge(A[1..m],p,q,r)（ Page 67） 輸入：數(shù)組 A[1..m]和它的三個索引 p,q,r（ 1≤p≤q＜ r≤m），二個子數(shù)組 A[p..q]和 A[q+1..r]各自按升序排列。 輸出：子數(shù)組 A[p..r]按升序排列。 1. ment:B[p..r]為輔助數(shù)組 //或 B[1..m] 2. s←p : t←q+1 : k←p //s和 t分別指向數(shù)組 A二個子數(shù)組元素 3. while (s≤q) and (t≤r) //k指向數(shù)組 B當前空白元素位置 4. if A[s]≤A[t] then B[k]←A[s] : s←s+1 5. else B[k]←A[t] : t←t+1 6. end if 7. k←k+1 //指向數(shù)組 B下一個空白位置 8. end while 9. if s=q+1 then B[k..r]←A[t..r] //子數(shù)組 A[p..q]元素已處理完 10. else B[k..r]←A[s..q] //否則 t=r+1,子數(shù)組 A[q+1..r]已處理完。 11. end if 12. A[p..r]← B[p..r] //復制 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ù)分別為 n1和 n2的二個子數(shù)組 n1+n2=n，如果子數(shù)組 A[p..q]中每個元素均小于另一個子數(shù)組 A[q+1,r]中的所有元素，例，要合并下面二個子數(shù)組： 2 3 6 7 11 13 45 57 該算法只需執(zhí)行 3次比較，即 n1次比較。 另一方面，比較次數(shù)最多為 n1= n1+n21次。例如要合并下面二個子數(shù)組： 2 3 66 7 11 13 45 57 就需要 7次比較。所以，算法 Merge的最少比較次數(shù)是n1，最大比較次數(shù)為 n1。 37 觀察結論 （ Page 7） 執(zhí)行算法 Merge，將個數(shù)分別為 n1和 n2的非空數(shù)組合并成一個為 n= n1+n2的排序數(shù)組。設n1≤n2 ，元素的比較次數(shù)在 n1和 n1之間。特例，如果二個數(shù)組大小為 ?n/2?和 ?n/2? ，需要比較的最大次數(shù)在 ?n/2?和 n1之間。 觀察結論 （ Page 7） 執(zhí)行算法 Merge，將個數(shù)分別為 n1和 n2的非空數(shù)組合并成一個為 n= n1+