第5章 減治法Decrease and conquer

1、第第5 5章章 減治法減治法( (Decrease and conquerDecrease and conquer） 1 2 3 4 減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 排序問題中的減治法排序問題中的減治法 組合問題中的減治法組合問題中的減治法 5 查找問題中的減治法查找問題中的減治法 小結(jié)小結(jié) 5.1 減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 分治法分治法是把一個大問題劃分為若干個子問題，是把一個大問題劃分為若干個子問題， 分別求解各個子問題，然后再把子問題的解進(jìn)行分別求解各個子問題，然后再把子問題的解進(jìn)行 合并得到原問題的解。合并得到原問題的解。 減治法減治法同樣是把一個大問題劃分為若干個子同樣是把

2、一個大問題劃分為若干個子 問題，但是這些子問題不需要分別求解，問題，但是這些子問題不需要分別求解，只需求只需求 解其中的一個子問題，因而也無需對子問題的解解其中的一個子問題，因而也無需對子問題的解 進(jìn)行合并進(jìn)行合并。 所以所以，嚴(yán)格地說，嚴(yán)格地說，減治法應(yīng)該是一種退化了減治法應(yīng)該是一種退化了 的分治法。的分治法。 5.1 減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 規(guī)模為規(guī)模為n的原問題的解與較小規(guī)模（通常是的原問題的解與較小規(guī)模（通常是 n/2）的子問題的解之間具有關(guān)系：）的子問題的解之間具有關(guān)系： （1）原問題的解只存在于其中一個較小規(guī)模的）原問題的解只存在于其中一個較小規(guī)模的 子問題中；子問題中；

3、 （2）原問題的解與其中一個較小規(guī)模的解之間）原問題的解與其中一個較小規(guī)模的解之間 存在某種對應(yīng)關(guān)系。存在某種對應(yīng)關(guān)系。 由于原問題的解與較小規(guī)模的子問題的解之由于原問題的解與較小規(guī)模的子問題的解之 間存在這種關(guān)系，所以，只需求解其中一個較小間存在這種關(guān)系，所以，只需求解其中一個較小 規(guī)模的子問題就可以得到原問題的解。規(guī)模的子問題就可以得到原問題的解。 子問題子問題 的規(guī)模是的規(guī)模是n/2 子問題的解子問題的解 原問題的解原問題的解 原問題原問題 的規(guī)模是的規(guī)模是n 5.1 減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 例：計(jì)算例：計(jì)算an的值的值 應(yīng)用應(yīng)用分治法分治法得到得到an的計(jì)算方法是：的計(jì)算方法

4、是： 1aa 1a a 22 n n nn n - 且是奇數(shù) 且是偶數(shù) 1)( 1)( 1 22 )1 ( 22 naa na na a n n n 應(yīng)用應(yīng)用減治技術(shù)減治技術(shù)得到如下計(jì)算方法：得到如下計(jì)算方法： 34 32 32 81 31 31 9 31 31 9 3 3 3 3 分解問題分解問題 求解每個子問題求解每個子問題 合并子問題的解合并子問題的解 分析時(shí) 間性能 1 1 22 naa na a nn n 如果如果 如果如果 應(yīng)用應(yīng)用分治技術(shù)計(jì)算分治技術(shù)計(jì)算an 。 T(n)=1 n=1 T(n)=2T(n/2)+1 n1 T(n)=O(n) 不是所有的分治法都比簡不是所有的分治法都

5、比簡 單的蠻力法有效單的蠻力法有效 應(yīng)用分治法（例如二分法）得到的算法通常具有應(yīng)用分治法（例如二分法）得到的算法通常具有 如下遞推式：如下遞推式： 分治法和減治法區(qū)別分治法和減治法區(qū)別 應(yīng)用減治法（例如減半法）得到的算法通常具有應(yīng)用減治法（例如減半法）得到的算法通常具有 如下遞推式：如下遞推式： 1 1 1)2/( 0 )( n n nT nT ( ) ( ) 2 ( / 2)c g nn T n T n 足夠小 O (log2n) O (n) 應(yīng)用分治法（例如二分法）得到的算法通常具有應(yīng)用分治法（例如二分法）得到的算法通常具有 如下遞推式：如下遞推式： 分治法和減治法區(qū)別分治法和減治法區(qū)別

6、應(yīng)用減治法（例如減半法）得到的算法通常具有應(yīng)用減治法（例如減半法）得到的算法通常具有 如下遞推式：如下遞推式： 11 ( ) ( / 2)O(n)1 n T n T nn ( ) ( ) 2 ( / 2)O(n) g nn T n T n 足夠小 O (n) O (nlogn) 5.2 查找問題中的減治法查找問題中的減治法 5.2.1 折半查找折半查找 5.2.2 二叉排序樹二叉排序樹 5.2.3 選擇問題選擇問題 問題描述：問題描述： 應(yīng)用折半查找方法在一個有序序列中應(yīng)用折半查找方法在一個有序序列中 查找值為查找值為k的記錄。若查找成功，返回記錄的記錄。若查找成功，返回記錄 k在序列中的位置

7、，若查找失敗，返回失敗在序列中的位置，若查找失敗，返回失敗 信息。信息。 5.2.1 5.2.1 折半查找折半查找 折半查找利用了記錄序列有序的特點(diǎn)，其查找過程是折半查找利用了記錄序列有序的特點(diǎn)，其查找過程是： 在在有序表中，取中間記錄作為比較對象，若給定值與中間記錄有序表中，取中間記錄作為比較對象，若給定值與中間記錄 的關(guān)鍵碼相等，則查找成功的關(guān)鍵碼相等，則查找成功； 若若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù) 查找查找； 若若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)

8、繼續(xù) 查找查找。 不斷不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄，重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄， 查找失敗。查找失敗。 r1 rmid- -1 rmid rmid+1 rn （mid=( (1+n) )/2） 如果如果krmid查找這里查找這里 k 折半折半查找過程查找過程 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 low=1high=13mid=7 high=6 mid=3 high=2 mid=1 3114 1814 714 low=2 mid=2 14=14 折

9、半折半查找實(shí)例查找實(shí)例 在有序在有序表中表中查找值為查找值為14的的過程如下：過程如下： 算法算法折半查找折半查找 1. low=1；high=n； /設(shè)置初始查找區(qū)間設(shè)置初始查找區(qū)間 2. 測試查找區(qū)間測試查找區(qū)間low，high是否存在，若不存在，則查找是否存在，若不存在，則查找 失敗；失敗； 否則否則 3. 取中間點(diǎn)取中間點(diǎn)mid=( (low+high) )/2; 比較比較k與與rmid 有有以下三種情以下三種情 況：況： 3.1 若若krmid，則，則low=mid+1；查找在右半?yún)^(qū)進(jìn)行，轉(zhuǎn)；查找在右半?yún)^(qū)進(jìn)行，轉(zhuǎn)2； 3.3 若若k=rmid，則查找成功，返回記錄在表中位置，則查找成

10、功，返回記錄在表中位置mid。 5.2.1 5.2.1 折半查找折半查找 判定樹判定樹描述折半查找的判定描述折半查找的判定過程過程 長度為長度為n的判定樹的構(gòu)造方法為：的判定樹的構(gòu)造方法為： （1）當(dāng)）當(dāng)n=0時(shí)，判定樹為空；時(shí)，判定樹為空； （2）當(dāng)）當(dāng)n0時(shí)，判定樹的根結(jié)點(diǎn)是有序表中序號時(shí)，判定樹的根結(jié)點(diǎn)是有序表中序號 為為mid=(n+1)/2的記錄，根結(jié)點(diǎn)的左子樹是與有序的記錄，根結(jié)點(diǎn)的左子樹是與有序 表表r1 rmid-1相對應(yīng)的判定樹，根結(jié)點(diǎn)的右子相對應(yīng)的判定樹，根結(jié)點(diǎn)的右子 樹是與樹是與rmid+1 rn相對應(yīng)的判定樹。相對應(yīng)的判定樹。 折半折半查找算法分析查找算法分析 具有具有

11、11個結(jié)點(diǎn)的判定樹個結(jié)點(diǎn)的判定樹 6 3 1 25 4 811 107 9 在表中查找任一記錄的過程，即是判定樹中從根結(jié)點(diǎn)到在表中查找任一記錄的過程，即是判定樹中從根結(jié)點(diǎn)到 該記錄結(jié)點(diǎn)的路徑，和給定值的比較次數(shù)等于該記錄結(jié)點(diǎn)在該記錄結(jié)點(diǎn)的路徑，和給定值的比較次數(shù)等于該記錄結(jié)點(diǎn)在 樹中的層數(shù)。樹中的層數(shù)。具有具有n個結(jié)點(diǎn)的判定樹的深度為個結(jié)點(diǎn)的判定樹的深度為 。 1log2n 折半查找判定樹折半查找判定樹 在在一個無序序列中執(zhí)行查找操作，可以將一個無序序列中執(zhí)行查找操作，可以將 無序序列建立一棵二叉查找樹，然后在二叉查無序序列建立一棵二叉查找樹，然后在二叉查 找樹中查找值為找樹中查找值為k的記錄

12、，若查找成功，返回的記錄，若查找成功，返回 記錄記錄k的存儲地址，若查找失敗，返回空指針。的存儲地址，若查找失敗，返回空指針。 5.2.2 5.2.2 二叉查找二叉查找樹樹 二二叉查找樹（叉查找樹（Binary Search Tree），也稱），也稱 二叉搜索樹、有序二叉樹（二叉搜索樹、有序二叉樹（ordered binary tree），）， 二叉二叉排序排序樹樹（sorted binary tree） 二叉查找樹的定義二叉查找樹的定義 二叉查找樹是指一棵空樹或者具有下列性質(zhì)的二二叉查找樹是指一棵空樹或者具有下列性質(zhì)的二 叉樹：叉樹： 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的若任意節(jié)點(diǎn)的

13、左子樹不空，則左子樹上所有結(jié)點(diǎn)的 值均小于或等于它的根結(jié)點(diǎn)的值；值均小于或等于它的根結(jié)點(diǎn)的值； 任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值 均大于它的根結(jié)點(diǎn)的值；均大于它的根結(jié)點(diǎn)的值； 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。 沒有鍵值相等的節(jié)點(diǎn)（沒有鍵值相等的節(jié)點(diǎn)（no duplicate nodes）。）。 (a) 按按63,90,55,58,70,42,10,45,83,67 (b) 按按55,42,10,70,63,58,83,67,90,45 的順序構(gòu)造的二叉查找樹的順序構(gòu)造的二叉查找樹 的順序構(gòu)造

14、的二叉查找樹的順序構(gòu)造的二叉查找樹 58 42 70 90 63 45 55 8367 10 10 8363 70 55 45 42 6758 90 二叉查找樹二叉查找樹 = 平衡二叉樹？平衡二叉樹？ 將無序序列建立一棵二叉查找樹將無序序列建立一棵二叉查找樹 由二叉查找樹的定義，在二叉查找樹由二叉查找樹的定義，在二叉查找樹root中查找給中查找給 定值定值k的過程是：的過程是： 若若root是空樹，則查找失?。皇强諛?，則查找失敗； 若若k根結(jié)點(diǎn)的值，則查找成功；根結(jié)點(diǎn)的值，則查找成功； 否則，若否則，若k根結(jié)點(diǎn)的值，則在根結(jié)點(diǎn)的值，則在root的左子樹上查找；的左子樹上查找； 否則，在否則，在

15、root的右子樹上查找；的右子樹上查找； 上述過程一直持續(xù)到上述過程一直持續(xù)到k被找到或者待查找的子樹為被找到或者待查找的子樹為 空，如果待查找的子樹為空，則查找失敗空，如果待查找的子樹為空，則查找失敗。 二叉查找樹二叉查找樹查找過程查找過程 二叉查找樹的查找效率就在于只需要查找兩個子樹二叉查找樹的查找效率就在于只需要查找兩個子樹之一之一 在二叉查找樹中查找關(guān)鍵字值為在二叉查找樹中查找關(guān)鍵字值為35，95的過程：的過程： 50 30 20 80 90 85 88 40 35 32 50 30 20 80 90 85 88 40 35 32 二叉查找樹二叉查找樹查找實(shí)例查找實(shí)例 簡述查找過程？簡

16、述查找過程？ 二叉查找樹二叉查找樹的結(jié)點(diǎn)結(jié)構(gòu)為：的結(jié)點(diǎn)結(jié)構(gòu)為： struct BiNode int data; /結(jié)點(diǎn)的值，假設(shè)查找集合的元素為整型結(jié)點(diǎn)的值，假設(shè)查找集合的元素為整型 BiNode *lchild, *rchild; /指向左、右子樹的指向左、右子樹的指針指針 ; 算法算法二叉查找樹二叉查找樹的查找的查找 BiNode * SearchBST(BiNode *root, int k) if (root= =NULL) return NULL； else if (root-data=k) return root; else if (kdata) return SearchBST(

17、root-lchild, k); else return SearchBST(root-rchild, k); 在二叉排序樹上查找關(guān)鍵碼等于給定值的結(jié)點(diǎn)的在二叉排序樹上查找關(guān)鍵碼等于給定值的結(jié)點(diǎn)的 過程，恰好走了一條從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑，和給過程，恰好走了一條從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑，和給 定值的比較次數(shù)等于給定值的結(jié)點(diǎn)在二叉排序樹中的定值的比較次數(shù)等于給定值的結(jié)點(diǎn)在二叉排序樹中的 層數(shù)，比較次數(shù)最少為層數(shù)，比較次數(shù)最少為1次（即整個二叉排序樹的根次（即整個二叉排序樹的根 結(jié)點(diǎn)就是待查結(jié)點(diǎn)），最多不超過樹的深度結(jié)點(diǎn)就是待查結(jié)點(diǎn)），最多不超過樹的深度。 具有具有n個結(jié)點(diǎn)的二叉樹的深度至少是個結(jié)點(diǎn)

18、的二叉樹的深度至少是 ， 至多是至多是n。所以所以，二叉排序樹的查找性能在二叉排序樹的查找性能在O( (log2n) ) 和和O( (n) )之間之間。 1log 2 n 二叉查找樹查找二叉查找樹查找性能分析性能分析 設(shè)設(shè)無序序列無序序列 T =(r1, r2, , rn)，T 的第的第k（1kn） 小元素定義為小元素定義為T按升序排列后在第按升序排列后在第k個位置上的元個位置上的元 素。給定一個序列素。給定一個序列T和一個整數(shù)和一個整數(shù)k，尋找，尋找 T 的第的第k小小 元素的問題稱為元素的問題稱為選擇問題選擇問題。 特別特別地，將尋找第地，將尋找第n/2小元素的問題稱為小元素的問題稱為中值

19、問題中值問題。 5.2.3 選擇問題選擇問題 問題描述：問題描述： 在在n個元素的無序數(shù)組中選擇第個元素的無序數(shù)組中選擇第k(1=k=n)小元素。小元素。 當(dāng)當(dāng)k=1時(shí)，相當(dāng)于找最小值。時(shí)，相當(dāng)于找最小值。 當(dāng)當(dāng)k=n時(shí)，相當(dāng)于找最大值。時(shí)，相當(dāng)于找最大值。 當(dāng)當(dāng)k=n/2時(shí)，稱中值。時(shí)，稱中值。 5.2.3 選擇問題選擇問題 （1）若）若k=s，則，則rs就是第就是第k小元素；小元素； （2）若）若ks，則第，則第k小元素一定在序列小元素一定在序列rs+1 rj中；中； 無論哪種情況，或者已經(jīng)得出結(jié)果（如果軸值恰好是序無論哪種情況，或者已經(jīng)得出結(jié)果（如果軸值恰好是序 列的中值），或者將選擇問

20、題的查找區(qū)間減少一半。列的中值），或者將選擇問題的查找區(qū)間減少一半。 ri rk rs- -1 rs rs+1 rj 均均rs 軸值軸值 均均rs ri rs- -1 rs rs+1 rk rj 均均rs 軸值軸值 均均rs (a) 若若ks，則，則rk在右半?yún)^(qū)在右半?yún)^(qū) 考慮考慮快速排序快速排序中的劃分過程，一般情況下，設(shè)待劃分中的劃分過程，一般情況下，設(shè)待劃分 的序列為的序列為ri rj，選定一個軸值將序列，選定一個軸值將序列ri rj進(jìn)行劃分，使進(jìn)行劃分，使 得比軸值小的元素都位于軸值的左側(cè)，比軸值大的元素都得比軸值小的元素都位于軸值的左側(cè)，比軸值大的元素都 位于軸值的右側(cè)，假定軸值的最終

21、位置是位于軸值的右側(cè)，假定軸值的最終位置是s，則：，則： 尋找尋找 第第k小元素問題小元素問題 選擇問題的例子選擇問題的例子 5 3 8 1 4 6 9 2 7 選擇問題的查找過程示例（選擇問題的查找過程示例（查找第查找第4小元素）小元素） 查找過程：以查找過程：以5為軸值劃分為軸值劃分 序列序列42 ，只在右側(cè)，只在右側(cè)查找，以查找，以4為軸為軸 值劃分值劃分序列序列44，軸值即，軸值即 為第為第4小元素小元素 2 3 4 1 5 6 9 8 7 2 3 4 1 1 2 4 3 4 3 3 4 A128=8,33,17,51,57,49,35,11,25,37,14,3,2,1A128=8,

22、33,17,51,57,49,35,11,25,37,14,3,2,1 3,52,12,6,29,32,54,5,16,22,23,7,61,36,93,52,12,6,29,32,54,5,16,22,23,7,61,36,9，求，求A A的的 中位數(shù)元素，即第中位數(shù)元素，即第1414小元素。小元素。(k=14)(k=14) 8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7,61,36,9 7,5,6,2,3,8,35,11,25,37,14,49,57,13,52,12,51,29,32,54,17,1

23、6,22,23,33,61,36,9 jk，在在左左邊區(qū)邊區(qū)間找第間找第k(=8)小元素小元素 j=6 j=14 35,11,25,37,14,49,57,13,52,12,51,29,32,54,17,16,22,23,33,61,36,9 選擇問題的例子選擇問題的例子 9,11,25,33,14,23,22,13,16,12,17,29,32 11,25,33,14,23,22,13,16,12,17,29,32 j=8 j=k=1，找到原問題第找到原問題第14小小元素元素22，結(jié)束。結(jié)束。 25,33,14,23,22,13,16,12,17,29,32 9,11,25,33,14,23

24、,22,13,16,12,17,29,32 jk，在在右邊右邊區(qū)間區(qū)間找第找第k(=8-1=7)小元素小元素 j=1 jk，在在左左邊區(qū)邊區(qū)間找第間找第k(=6)小元素小元素 17,12,14,23,22,13,16 16,12,14,13,17,22,23 j=5 jk，在右邊區(qū)間在右邊區(qū)間找第找第k(=6-5=1)小元素小元素 22,23 算法算法選擇問題選擇問題 1. i=1; j=n; /設(shè)置初始查找區(qū)間設(shè)置初始查找區(qū)間 2. 以以ri為軸值對序列為軸值對序列rirj進(jìn)行一次劃分，得進(jìn)行一次劃分，得 到軸值的位置到軸值的位置s; 3. 將軸值位置將軸值位置s與與k比較比較 3.1 如果

25、如果k=s，則將，則將rs作為結(jié)果返回；作為結(jié)果返回； 3.2 否則，如果否則，如果ks，則，則j=s-1，轉(zhuǎn)步驟，轉(zhuǎn)步驟2； 3.3 否則，否則，i=s+1，轉(zhuǎn)步驟，轉(zhuǎn)步驟2； 5.2.3 選擇問題選擇問題 算法算法選擇問題選擇問題 int Partition(int r , int low, int high) /快速排序劃分 int i = low, j=high; /初始化待劃分區(qū)間 while (i j) while (i j /右側(cè)掃描 if (i j) int temp = ri;ri = rj;rj = temp;/將較小記錄交換到前面 i+; while (i j /左側(cè)掃描

26、 if (i k) return MinK(r, low, s-1, k); else return MinK(r, s+1, high, k); int main() int r=5,3,8,1,10,6,9,12,17,4,15,22; int k = 6; int x = MinK(r,0,11,k-1); cout第k小的元素是xendl; return 0; 習(xí)題 5,3,8,1,10,6,9,12,17,4,15,22 求第求第k（k= 6）小元素）小元素; 5,3,8,1,10,6,9,12,17,4,15,22 4,3,1,5,10,6,9,12,17,8,15,22 10,6

27、,9,12,17,8,15,22 jk，在左邊區(qū)間在左邊區(qū)間找第找第k(=2)小元素小元素 j=4 8,6,9 j=k，找到原問題，找到原問題第第6小元素小元素8，結(jié)束。結(jié)束。 j=2 6,8,9 最好情況最好情況：每次劃分的軸值恰好是序列的中值，則可以保證處每次劃分的軸值恰好是序列的中值，則可以保證處 理的區(qū)間比上一次減半，由于在理的區(qū)間比上一次減半，由于在一次一次劃分（劃分（O(n)O(n)）后后，只需處，只需處 理一個子序列，所以，比較次數(shù)的遞推式是：理一個子序列，所以，比較次數(shù)的遞推式是： )()()2()(nOnOnTnT 最壞情況最壞情況：每次劃分的軸值恰好是序列中的最大值或最小值

28、，每次劃分的軸值恰好是序列中的最大值或最小值， 則處理區(qū)間只能比上一次減少則處理區(qū)間只能比上一次減少1個，所以，比較次數(shù)的遞推式個，所以，比較次數(shù)的遞推式 是：是： 平均情況平均情況：假設(shè)每次劃分的軸值是劃分序列中的一個隨機(jī)位：假設(shè)每次劃分的軸值是劃分序列中的一個隨機(jī)位 置的元素，則處理區(qū)間按照一種隨機(jī)的方式減少，可以證明，置的元素，則處理區(qū)間按照一種隨機(jī)的方式減少，可以證明， 算法的平均時(shí)間是算法的平均時(shí)間是O(n) 。 ) 2 ()() 1()(nOnOnTnT- 5.2.3 選擇選擇問題算法分析問題算法分析 如果如果能在線性時(shí)間內(nèi)找到一個劃分基準(zhǔn)，使能在線性時(shí)間內(nèi)找到一個劃分基準(zhǔn)，使 得

29、按這個基準(zhǔn)所劃分出的得按這個基準(zhǔn)所劃分出的2個子數(shù)組的長度都至個子數(shù)組的長度都至 少為原數(shù)組長度的少為原數(shù)組長度的倍倍(0 x x 時(shí)間復(fù)雜性時(shí)間復(fù)雜性O(shè) O( (n n) ) 線性時(shí)間選擇線性時(shí)間選擇 第五步第五步: :遞歸遞歸 設(shè)設(shè)x x是中位數(shù)的中位數(shù)是中位數(shù)的中位數(shù)( (MoMMoM),),劃分完成后其下標(biāo)為劃分完成后其下標(biāo)為k k 如果如果i i= =k,k,則返回則返回x x 如果如果i i k,k,則在第三個部分遞歸選取第則在第三個部分遞歸選取第( (i i- -k k) )大的數(shù)大的數(shù) x i then return Select(A1:k-1,i);7. else if ki

30、 then return Select(A1:k-1,i); 8. else return Select(Ak+1:n,i-k);8. else return Select(Ak+1:n,i-k); 第一步 第二步 第三步 第四步 第五步 線性時(shí)間線性時(shí)間選擇算法選擇算法 算法算法Select(Select(A,iA,i) ) Input: Input: 數(shù)組數(shù)組A1:n, A1:n, 1 1 i i n n Output: A1:nOutput: A1:n中的第中的第i-i-大的數(shù)大的數(shù) 1. for j1. for j 1 to n/51 to n/5 2. 2. InsertSortIn

31、sertSort(A(j-1)(A(j-1)* *5+1 : (j-1)5+1 : (j-1)* *5+5);5+5); 3. 3. swap(Ajswap(Aj, , A(j-1)A(j-1)* *5+3);5+3); 4. 4. x x Select(A1: n/5,n/10 );Select(A1: n/5,n/10 ); 5. k 5. k partition(A1:n,x);partition(A1:n,x); 6. if k=i then return x;6. if k=i then return x; 7. else if ki then return Select(A1:k-

32、1,i);7. else if ki then return Select(A1:k-1,i); 8. else return Select(Ak+1:n,i-k);8. else return Select(Ak+1:n,i-k); 第一步 O(n) T( n n/ /5 5 ) ) O(n) ? 線性時(shí)間選擇線性時(shí)間選擇 觀察第五步的處理過程觀察第五步的處理過程 線性時(shí)間選擇線性時(shí)間選擇 第五步至少刪除了 3 3n n/10/10 個數(shù)個數(shù) n- 3 3n n/10/10 3 3n n/4 /4 如果時(shí)間復(fù)雜度是輸入規(guī)模的遞增函數(shù)如果時(shí)間復(fù)雜度是輸入規(guī)模的遞增函數(shù) 則第五步的時(shí)間開銷不超過

33、則第五步的時(shí)間開銷不超過T T(3(3n n/4)/4) 線性時(shí)間選擇線性時(shí)間選擇 Type Select(Type a, int p, int r, int k) if (r-p75) 用某個簡單排序算法對數(shù)組用某個簡單排序算法對數(shù)組ap:r排序排序; return ap+k-1; for ( int i = 0; i=(r-p-4)/5; i+ ) 將將ap+5*i至至ap+5*i+4的第的第3小元素小元素 與與ap+i交換位置交換位置; /找中位數(shù)的中位數(shù)，找中位數(shù)的中位數(shù)，r-p-4即上面所說的即上面所說的n-5 Type x = Select(a, p, p+(r-p-4)/5, (

34、r-p-4)/10); int i=Partition(a,p,r, x), j=i-p+1; if (k=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j); 復(fù)雜度分析復(fù)雜度分析 T(n)=O(n) 75 75 )4/3()5/( )( 2 1 n n nTnTnC C nT 上述算法將每一組的大小定為上述算法將每一組的大小定為5，并選取，并選取75作為是否作遞歸作為是否作遞歸 調(diào)用的分界點(diǎn)。這調(diào)用的分界點(diǎn)。這2點(diǎn)保證了點(diǎn)保證了T(n)的遞歸式中的遞歸式中2個自變量之和個自變量之和 n/5+3n/4=19n/20=n，06，

35、不能直接找，進(jìn)入不能直接找，進(jìn)入(2)； (2)按按5個一組分組個一組分組： (8,33,17,51,57);(49,35,11,25,37);(14,3,2,13,52);(12,6,29,32,54); (5,16,22,23,7)。 (3)每組按升序排序：每組按升序排序： (8,17,33,51,57);(11,25,35,37,49);(2,3,13,14,52);(6,12,29,32,54); (5,7,16,22,23)。 (4)中值的集合中值的集合M=33,35,13,29,16。 (5)遞歸找到中值的中值遞歸找到中值的中值m=29。 線性時(shí)間選擇算法線性時(shí)間選擇算法 (6)把

36、把A分為三組：分為三組： A1= 8,17,11,25,14,3,2,13,12,6,5,16,22,23,7,9; A2=29; A3=33,51,57,49,35,37,52,32,54,61,36。 因?yàn)橐驗(yàn)閗=14|A1|+|A2|=11，丟掉，丟掉A1和和A2，而第，而第14小元小元 素必然在素必然在A3中。中。 (13)設(shè)設(shè)A=A3=17,25,16,22,23 然后在然后在A3中找第中找第k(=14-11=3)小元素。小元素。 (14) A3=17,25,16,22,23，由于，由于|A3|6，所以直接找，所以直接找 到第到第3小元素為小元素為22。 因此，原問題的中值是因此，原

37、問題的中值是22。 解畢。解畢。 線性時(shí)間選擇算法線性時(shí)間選擇算法 習(xí)題 設(shè)數(shù)組設(shè)數(shù)組A有有16個個元素元素如下如下 5,3,8,1,10,6,9,12,17,4,15,22,11,13,16,30 求第求第k（k=6）小元素）小元素; 5個分為一組，閾值為個分為一組，閾值為6。 5,3,8,1,106,9,12,17,415,22,11,13,16 中值的集合中值的集合5,9,15 找到找到中值的中中值的中值值9 5,3,8,1,6,410,12,17,15,22,11,13,16,30 找到第找到第6小小元素元素為為8 ，結(jié)束。結(jié)束。 9 5,3,8,1,64 3,1,458,6 5.3

38、排序問題中的減治法排序問題中的減治法 5.3.1 插入插入排序排序( (減一技術(shù)減一技術(shù)) ) 5.3.2 堆排序堆排序 5.3.1 插入插入排序排序( (減一技術(shù)減一技術(shù)) ) 【問題問題】應(yīng)用插入排序方法對一個記錄序列進(jìn)行應(yīng)用插入排序方法對一個記錄序列進(jìn)行 升序排列。升序排列。 【想法想法】插入排序?qū)儆跍p治法的減一技術(shù)，即每插入排序?qū)儆跍p治法的減一技術(shù)，即每 一趟排序后將問題規(guī)模減少一趟排序后將問題規(guī)模減少1，其基本思想是：，其基本思想是： 依次將待排序序列中的每一個記錄插入到一個已依次將待排序序列中的每一個記錄插入到一個已 排好序的序列中，直到全部記錄都排好序。排好序的序列中，直到全部記

39、錄都排好序。 【算法分析算法分析】T(n) = O(n2)。 堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點(diǎn)的值堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點(diǎn)的值 都小于或等于其左右孩子結(jié)點(diǎn)的值（小根堆）；都小于或等于其左右孩子結(jié)點(diǎn)的值（小根堆）； 或者每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)或者每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn) 的值（大根堆）。如果將具有的值（大根堆）。如果將具有n個結(jié)點(diǎn)的堆按層個結(jié)點(diǎn)的堆按層 序從序從1開始編號，則結(jié)點(diǎn)之間滿足如下關(guān)系：開始編號，則結(jié)點(diǎn)之間滿足如下關(guān)系： 【問題描述問題描述】應(yīng)用堆排序方法對一個記錄序列進(jìn)應(yīng)用堆排序方法對一個記錄序列進(jìn) 行升序排列。行升序排列。 kik2

40、i kik2i+1 kik2i kik2i+1 1in/2 或 5.3.2 堆排序堆排序 以結(jié)點(diǎn)的編號作為下標(biāo)，將堆用順序存儲結(jié)構(gòu)（即數(shù)組）以結(jié)點(diǎn)的編號作為下標(biāo)，將堆用順序存儲結(jié)構(gòu)（即數(shù)組） 來存儲，則堆對應(yīng)于一組序列。來存儲，則堆對應(yīng)于一組序列。 (a) 大根堆及其對應(yīng)的序列大根堆及其對應(yīng)的序列(b) 小根堆及其對應(yīng)的序列小根堆及其對應(yīng)的序列 47 35 26 20 18 7 13 107 10 13 18 35 26 47 20 47 3526 1318 20 7 10 26 1013 4735 18 7 20 5.3.2 堆排序堆排序 堆排序的基本思想是：首先將待排序的記錄序列構(gòu)造成堆排

41、序的基本思想是：首先將待排序的記錄序列構(gòu)造成 一個堆，此時(shí)，選出了堆中所有記錄的最大者即堆頂記錄，一個堆，此時(shí)，選出了堆中所有記錄的最大者即堆頂記錄， 然后將它從堆中移走（通常將堆頂記錄和堆中最后一個記錄然后將它從堆中移走（通常將堆頂記錄和堆中最后一個記錄 交換），并將剩余的記錄再調(diào)整成堆，這樣又找出了次大的交換），并將剩余的記錄再調(diào)整成堆，這樣又找出了次大的 記錄，以此類推，直到堆中只有一個記錄為止。記錄，以此類推，直到堆中只有一個記錄為止。 r1 r2 ri ri+1 rn-1 rn 無序區(qū) 有序區(qū) 為一個堆 已經(jīng)位于最終位置 堆頂和堆中最后堆頂和堆中最后 一個記錄交換一個記錄交換 堆排序

42、堆排序想法想法 堆調(diào)整問題堆調(diào)整問題：將一個無序序列調(diào)整為堆：將一個無序序列調(diào)整為堆 （1）篩選法調(diào)整堆）篩選法調(diào)整堆 關(guān)鍵問題：完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是關(guān)鍵問題：完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是 堆，如何調(diào)整根結(jié)點(diǎn)，使整個完全二叉樹成為一個堆？堆，如何調(diào)整根結(jié)點(diǎn)，使整個完全二叉樹成為一個堆？ (a) 28與與35交換交換(b) 28與與32交換交換(c) 將將28篩到葉子篩到葉子 28 3218 20 1218 20 12 35 32 18 20 12 35 35 28 32 28 5.3.2 堆排序堆排序 堆排序堆排序?qū)嵗龑?shí)例 28 2516 32 1836 16 32 16

43、28 25 1836 25 32 16 28 18 36 25 28 32 36 28 161825 假設(shè)當(dāng)前要篩選結(jié)點(diǎn)的編號為假設(shè)當(dāng)前要篩選結(jié)點(diǎn)的編號為k，堆中最后一個結(jié)點(diǎn)的，堆中最后一個結(jié)點(diǎn)的 編號為編號為n，并且結(jié)點(diǎn)，并且結(jié)點(diǎn)k的左右子樹均是堆（即的左右子樹均是堆（即rk+1 rn滿滿 足堆的條件），則篩選算法用偽代碼可描述為：足堆的條件），則篩選算法用偽代碼可描述為： 算法算法篩選法調(diào)整堆篩選法調(diào)整堆 1. 設(shè)置設(shè)置i和和j，分別指向當(dāng)前要篩選的結(jié)點(diǎn)和要篩選結(jié)點(diǎn)的左孩子；，分別指向當(dāng)前要篩選的結(jié)點(diǎn)和要篩選結(jié)點(diǎn)的左孩子； 2. 若結(jié)點(diǎn)若結(jié)點(diǎn)i已是葉子，則篩選完畢；否則，比較要篩選結(jié)點(diǎn)的已

44、是葉子，則篩選完畢；否則，比較要篩選結(jié)點(diǎn)的左右孩左右孩 子子結(jié)點(diǎn)，并將結(jié)點(diǎn)，并將j指向關(guān)鍵碼較大的結(jié)點(diǎn)；指向關(guān)鍵碼較大的結(jié)點(diǎn)； 3. 將要篩選結(jié)點(diǎn)將要篩選結(jié)點(diǎn)i的關(guān)鍵碼與結(jié)點(diǎn)的關(guān)鍵碼與結(jié)點(diǎn)j的關(guān)鍵碼進(jìn)行比較，有以下兩種情的關(guān)鍵碼進(jìn)行比較，有以下兩種情 況：況： 3.1 如果結(jié)點(diǎn)如果結(jié)點(diǎn)i的關(guān)鍵碼大，則完全二叉樹已經(jīng)是堆；的關(guān)鍵碼大，則完全二叉樹已經(jīng)是堆； 3.2 否則將否則將ri與與rj交換；令交換；令i=j，轉(zhuǎn)步驟，轉(zhuǎn)步驟2繼續(xù)進(jìn)行篩選。繼續(xù)進(jìn)行篩選。 時(shí)間性能是O(log2n)。 5.3.2 堆排序堆排序 算法算法篩選法調(diào)整堆篩選法調(diào)整堆 void SiftHeap( (int r , i

45、nt k, int n) ) i=k; j=2*i; /置置i為要篩的結(jié)點(diǎn)，為要篩的結(jié)點(diǎn)，j為為i的左孩子的左孩子 while ( (j=n) ) /篩選還沒有進(jìn)行到葉子篩選還沒有進(jìn)行到葉子 if ( (jn else rirj; /將根結(jié)點(diǎn)與結(jié)點(diǎn)將根結(jié)點(diǎn)與結(jié)點(diǎn)j交換交換 i=j; j=2*i; /被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)j的位置的位置 32 18 20 12 40 35 8 28 20 32 18 20 12 40 8 20 35 28 18 20 12 40 8 20 35 28 32 (a) 35與與28交換交換 (b) 35與與32交換交換 (c) 3540調(diào)整完畢調(diào)整

46、完畢 （2 2）插入法調(diào)整堆）插入法調(diào)整堆 關(guān)鍵問題是：在堆中插入一個結(jié)點(diǎn)，如何調(diào)整被插入結(jié)點(diǎn)，關(guān)鍵問題是：在堆中插入一個結(jié)點(diǎn)，如何調(diào)整被插入結(jié)點(diǎn)， 使整個完全二叉樹仍然是一個堆？使整個完全二叉樹仍然是一個堆？ 5.3.2 堆排序堆排序 假設(shè)當(dāng)前堆中有假設(shè)當(dāng)前堆中有k個結(jié)點(diǎn)，則要插入結(jié)點(diǎn)的編號為個結(jié)點(diǎn)，則要插入結(jié)點(diǎn)的編號為k+1， 插入法調(diào)整堆的算法如下：插入法調(diào)整堆的算法如下： 算法算法插入法調(diào)整堆插入法調(diào)整堆 1. 設(shè)設(shè)i指向當(dāng)前要插入的結(jié)點(diǎn)；指向當(dāng)前要插入的結(jié)點(diǎn)； 2. 若結(jié)點(diǎn)若結(jié)點(diǎn)i是整個堆的根結(jié)點(diǎn)，則調(diào)整完畢；是整個堆的根結(jié)點(diǎn)，則調(diào)整完畢； 3否則，設(shè)否則，設(shè)j指向結(jié)點(diǎn)指向結(jié)點(diǎn)i的雙親結(jié)點(diǎn)；將結(jié)點(diǎn)的雙親結(jié)點(diǎn)