算法設(shè)計與分析 王紅梅 第二版 第5章_ 減治法

1、教學重點教學重點減治法的設(shè)計思想，各種經(jīng)典問題的減治思想減治法的設(shè)計思想，各種經(jīng)典問題的減治思想教學難點教學難點二叉查找樹，堆排序二叉查找樹，堆排序教學內(nèi)容教學內(nèi)容及目標及目標知識點知識點教學要求教學要求了解了解理解理解掌握掌握熟練掌握熟練掌握減治法的設(shè)計思想減治法的設(shè)計思想折半查找折半查找二叉查找樹二叉查找樹選擇問題選擇問題插入排序插入排序堆排序堆排序淘汰賽冠軍問題淘汰賽冠軍問題假幣問題假幣問題1122naanaannn111)2/(0)(nnnTnT對比分治法：對比分治法： 足夠小nnfnTngnT)()2/(2)()(步驟步驟操作說明操作說明序列序列A序列序列B1初始序列初始序列11,

2、13, 15, 17, 192, 4, 10, 15, 202分別求中位數(shù)分別求中位數(shù)11, 13, 15, 17, 192, 4, 10, 15, 2031510，結(jié)果在，結(jié)果在10, 15之間之間舍棄舍棄15之后元素，之后元素，11,13,15舍棄舍棄10之前元素，之前元素，10,15,204分別求中位數(shù)分別求中位數(shù)11,13,1510,15,2051315，結(jié)果在，結(jié)果在11, 15之間之間舍棄舍棄13之前元素，之前元素，13,15舍棄舍棄15之后元素，之后元素，10,156分別求中位數(shù)分別求中位數(shù)13,1510,1571013，結(jié)果在，結(jié)果在10, 13之間之間舍棄舍棄13之后元素，之

3、后元素，13舍棄舍棄10之前元素，之前元素，158長度為長度為1，較小者為所求，較小者為所求13151log2nC+描述按按63,90,55,58,70,42,10,45,83,67順序構(gòu)造的二叉排序樹順序構(gòu)造的二叉排序樹584270906345558367101log2n算法算法選擇問題選擇問題輸入：無序序列輸入：無序序列r ，位置，位置k輸出：返回第輸出：返回第k小的元素值小的元素值 1. i=1; j=n; /設(shè)置初始查找區(qū)間設(shè)置初始查找區(qū)間 2. 以以ri為軸值對序列為軸值對序列rirj進行一次劃分，得到軸進行一次劃分，得到軸值的位置值的位置s; 3. 將軸值位置將軸值位置s與與k比較

4、比較 3.1 如果如果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；( )(2)( )( )T nT nO nO nr1r2ri-1r1r2ri-1ri 初始：（初始：（49）38 13 76 27 49 （38 49）13 76 27 49 （13 38 49）76 27 49 （13 38 49 76）27 49 （13 27 38 49 76 ）49 （13 27 38 49 49 76 ）212125插入排序插入排序2522222522211025211510

5、2525*2521151025*252118151018101825*25插入排序算法性能分析插入排序算法性能分析插入排序算法性能分析插入排序算法性能分析12121kknkkn221knk2log11log2nk1 19 98 810106 616162 211114 45 5n=10，故從第，故從第 10/2 5個結(jié)點開始進行調(diào)整個結(jié)點開始進行調(diào)整 1 19 98 810106 616162 211115 54 41 19 98 810106 611112 216165 54 41 19 98 810106 611112 216165 54 41 19 98 810106 611111616

6、2 25 54 41 19 98 810106 62 2161611115 54 416169 98 810106 62 21 111115 54 416169 98 810106 62 211111 15 54 416169 98 81 16 62 2111110105 54 4qRi左、右子樹是堆，子樹的根為各自子樹中關(guān)鍵字最大者，左、右子樹是堆，子樹的根為各自子樹中關(guān)鍵字最大者，q將將Ri和其左、右孩子中關(guān)鍵字最大者進行比較。和其左、右孩子中關(guān)鍵字最大者進行比較。若若Ri最大，則無需調(diào)整，以其為根的子樹已是堆；最大，則無需調(diào)整，以其為根的子樹已是堆；否則，將否則，將Ri和具有最大關(guān)鍵字的

7、左孩子和具有最大關(guān)鍵字的左孩子R2i或右孩子或右孩子R2i+1進行交換。進行交換。q交換后以交換后以R2i和和R2i+1為根的子樹可能不再是堆，但其左、為根的子樹可能不再是堆，但其左、右子樹仍然是堆，于是重復上述過程，右子樹仍然是堆，于是重復上述過程，將子樹調(diào)整為堆將子樹調(diào)整為堆，如此逐層遞推下去，最多可能一直調(diào)整到樹葉。如此逐層遞推下去，最多可能一直調(diào)整到樹葉。q這一過程就像過篩子一樣，把較小的關(guān)鍵字篩下去，而將最大這一過程就像過篩子一樣，把較小的關(guān)鍵字篩下去，而將最大關(guān)鍵字一層層地選擇上來。關(guān)鍵字一層層地選擇上來。 大根堆大根堆C+描述16169 98 81 16 62 2111110105 54 44 49 98 81 16 62 2111110105 511119 98 81 16 62 210104 45 52 29 98 81 16 610104 45 510109 98 81 16 65 54 42 21 19 98 86 65 54 42 29 98 81 16 65 54 42 21 18 86 65 54 42 28 86 61 15 54 42 21 16 65 54 42 26 61 15 54 42 22 21 15 54 45 51 14 42 22 21 14 44 41 12 21 12 22 21 11 112( )2 ( /