【正文】 ableListT::BSearch(const Tamp。 x, int left,int right)const 后置條件 : 在范圍為 [left,right]的表中搜索與 x有相同關(guān)鍵字值的元素；如果存在該元素，則函數(shù)返回該元素在表中的位置，否則函數(shù)返回－ 1，表示搜索失敗。 21 【 程序 5－ 6】 二分搜索算法框架 template class T int SortableListT::BSearch(const Tamp。 x, int left,int right)const { if (left=right){ int m=Divide(left+right)。 if (xl[m]) return BSearch(x,left,m1)。 else if (xl[m]) return BSearch(x,m+1,right)。 else return m。 } return 1。 } 22 對半搜索 對半搜索 對半搜索是一種二分搜索 。 設(shè)當(dāng)前搜索的子表 為 （ aleft,aleft+1,… ,aright） ， 令 m=(left+right)/2 23 【 程序 5－ 7】 對半搜索遞歸算法 template class T int SortableListT::BSearch(const Tamp。 x, int left, int right)const { if (left=right){ int m=(left+right)/2。 if (xl[m]) return BSearch(x,left,m1)。 else if (xl[m]) return BSearch(x,m+1,right)。 else return m。 } return 1。 } 24 定理 5－ 3 對于 n?0， 程序 5－ 7的對半搜索遞歸函數(shù)BSearch是正確的 。 25 二叉判定樹 二分搜索過程的算法行為可以用一棵二叉樹來描述。通常稱這棵描述搜索算法執(zhí)行過程的二叉樹為 二叉判定樹 (binary decision tree)。 26 27 性質(zhì) 5－ 1 具有 n個(gè)內(nèi)結(jié)點(diǎn)的對半搜索二叉判定樹的左子樹上有 ?(n1)/2?個(gè)內(nèi)結(jié)點(diǎn) ， 右子樹上有 ?n/2?個(gè)內(nèi)結(jié)點(diǎn) 。 性質(zhì) 5－ 2 具有 n(n0） 個(gè)內(nèi)結(jié)點(diǎn)的二叉判定樹的高度為?log n?+1 （ 不計(jì)外結(jié)點(diǎn) ） 。 28 性質(zhì) 5－ 3 若 n=2h1， 則對半搜索二叉判定樹是滿二叉樹 。 性質(zhì) 5－ 4 若 n=2h1， 則對半搜索二叉判定樹的外結(jié)點(diǎn)均在h+1層上 ， 否則 ， 在第 h或 h+1層上 ， h=?log n?+1。 29 定理 5－ 4 對半搜索算法在成功搜索的情況下 ， 關(guān)鍵字值之間的比較次數(shù)不超過 ?log n?+1。 對于不成功的搜索 ，算法需要作 ?log n?或 ?log n?+1次比較 。 定理 5－ 5 對半搜索算法在搜索成功時(shí)的平均時(shí)間復(fù)雜度為?(log n)。 30 搜索算法的時(shí)間下界 定理 5－ 6 在一個(gè)有 n個(gè)元素的集合中 ， 通過關(guān)鍵字值之間的比較 ， 搜索指定關(guān)鍵字值的元素 ， 任意這樣的算法在最壞情況下至少需要作 ?log n?+1次比較 。 31 排序問題 32 問題 排序是將一個(gè)元素序列調(diào)整為按指定關(guān)鍵字值的遞增（或遞減）次序排列的有序序列。 33 合并排序 合并兩個(gè)有序序列 兩路合并排序的基本運(yùn)算是把兩個(gè)有序序列合并成一個(gè)有序序列 。 34 【 程序 5－ 9】 Merge函數(shù) template class T void SortableListT::Merge(int left, int mid,int right) { T* temp=new T[rightleft+1]。 int i=left,j=mid+1,k=0。 while (( i=mid )amp。amp。 (j=right)) if (l[i]=l[j]) temp[k++]=l[i++]。 else temp[k++]=l[j++]。 while (i=mid) temp[k++]=l[i++]。 while (j=right) temp[k++]=l[j++]。 for (i=0,k=left。k=right。) l[k++] = temp[i++]。 } 35 36 分治法求解 將待排序的元素序列一分為二分 ， 得到兩個(gè)長度基本相等的子序列 ， 如同對半搜索的做法；然后對兩個(gè)子序列分別排序 ， 如果子序列較長 ， 還可繼續(xù)細(xì)分 ， 直到子序列的長度不超過 1為止；當(dāng)分解所得的子序列已排列有序 ， 可以采用上面介紹的將兩個(gè)有序子序列 ， 合并成一個(gè)有序子序列的方法 ， 實(shí)現(xiàn)將子問題的解組合成原問題解 ， 這是分治法不可缺少的一步 。 37 【 程序 5－ 10】 兩路 合并排序 template class T void SortableListT::MergeSort(int left,int right) { if (leftright) { int mid = (left+right)/2。 MergeSort(left,mid)。 MergeSort(mid+1,right)。 Merge(left,mid,right)。 } } 38 39 性能分析 合并排序遞歸算法的時(shí)間復(fù)雜度為 O(n log n)。 ??????? 1n )2/n(T21n d)n(T40 快速排序 快速排序采用一種特殊的分劃操作對排序問題進(jìn)行分解，其分解方法是：在待排序的序列(K0,K1,…, Kn1)中選擇一個(gè)元素作為分 劃元素 ，也稱為 主元 （ pivot）。不妨假定選擇 K?為主元。經(jīng)過一趟特殊的分劃處理將原序列中的元素 重新排列 ，使得以主元為軸心，將序列分成左右兩個(gè)子序列。主元左測子序列中所有元素都不大于主元，主元右測子序列中所有元素都不小于主元。 41 分劃操作 42 【 程序 5－ 11】 分劃函數(shù) template class T int SortableListT::Partition(int left, int right) {//前置條件： left?right