教師發(fā)展中心名師示范課程聽(tīng)課記錄（五）

1、教師發(fā)展中心名師示范課程聽(tīng)課記錄（五）何欽銘：排序與哈希查找何欽銘：排序與哈希查找教學(xué)主題教學(xué)主題排序與哈希查找課堂性質(zhì)課堂性質(zhì)計(jì)算機(jī)及相關(guān)專業(yè)專業(yè)基礎(chǔ)課授課對(duì)象授課對(duì)象計(jì)算機(jī)學(xué)院本科生，觀摩師生授課教師授課教師何欽銘教授職稱職稱計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院系統(tǒng)結(jié)構(gòu)與網(wǎng)絡(luò)安全研究所博導(dǎo)上課時(shí)間上課時(shí)間2012年11月2日8:009:35上課地點(diǎn)上課地點(diǎn)紫金港校區(qū)東1B308內(nèi)容提要：內(nèi)容提要：（1）大數(shù)據(jù)排序、排序最壞時(shí)間復(fù)雜性下限以及基數(shù)排序

2、。）大數(shù)據(jù)排序、排序最壞時(shí)間復(fù)雜性下限以及基數(shù)排序。解決大數(shù)據(jù)結(jié)構(gòu)對(duì)象的排序問(wèn)題有兩個(gè)要點(diǎn)，一是記錄對(duì)象的下標(biāo)，排序時(shí)不交換對(duì)象本身而是交換對(duì)象下標(biāo)；二是通過(guò)環(huán)形移動(dòng)恢復(fù)排序好的下標(biāo)序列為對(duì)象序列?；诒容^和交換的排序算法的最壞時(shí)間復(fù)雜性下線是nlogn?；鶖?shù)排序是基于多鍵碼的排序算法。使用排序算法要考慮它的時(shí)間復(fù)雜性、穩(wěn)定性和空間復(fù)雜性。（2）哈希查找。）哈希查找。面對(duì)動(dòng)態(tài)的數(shù)據(jù)集合，要使用動(dòng)態(tài)查找方法，哈希查找是一種解決動(dòng)態(tài)查找問(wèn)題

3、的算法。哈希查找有兩個(gè)要點(diǎn)，一是構(gòu)造分布均勻的映射函數(shù)，二是想辦法解決可能的沖突。函數(shù)設(shè)計(jì)和沖突解決有多種方法，因此必須考慮它們的有效性。教學(xué)片斷紀(jì)實(shí)教學(xué)片斷紀(jì)實(shí)NotesP1：PPT頁(yè)碼第一部分：排序第一部分：排序P1：復(fù)習(xí)：復(fù)習(xí)歸并排序和快速排序，這兩個(gè)算法的基本思想都是基于分治法的思想：把大問(wèn)題分解為小問(wèn)題來(lái)解決，比如對(duì)n個(gè)數(shù)據(jù)分成兩堆，對(duì)這兩堆數(shù)據(jù)分別進(jìn)行排序，對(duì)兩堆進(jìn)行排序后可以遞歸做，再把兩堆從小到大的數(shù)據(jù)合在一起，變成原數(shù)

4、據(jù)從小到大排列的結(jié)果。最核心的步驟有三步：分解數(shù)據(jù)、遞歸、合并解，最主要的步驟是第一步和第三步。兩個(gè)典型算法的區(qū)別是分解問(wèn)題的方法不同。歸并排序是自然地將元素分為數(shù)量相等的兩部分，分別完成每一部分的排序后再合并。快速排序，每一步基于一個(gè)元素（基準(zhǔn)元素）將所有元素分為較大的部分和較小的部分，對(duì)這兩部分分別進(jìn)行排序。所以兩者的區(qū)別是重點(diǎn)不同，快速排序的重點(diǎn)在于怎么分解問(wèn)題，而歸并排序的重點(diǎn)放在第三步。P2：大數(shù)據(jù)結(jié)構(gòu)對(duì)象的排序：大數(shù)據(jù)結(jié)構(gòu)對(duì)

5、象的排序排序的基本特征就是對(duì)象之間的比較，發(fā)現(xiàn)位置不對(duì)就發(fā)生交換，所以比較和交換是之前的排序算法中的基本操作。在這種排序過(guò)程中會(huì)碰到一個(gè)問(wèn)題，如果排序的對(duì)象很大，因?yàn)閷?duì)象可能不僅僅是一個(gè)整數(shù)，可能代表了一個(gè)對(duì)象的信息，這個(gè)對(duì)象信息就是一個(gè)結(jié)構(gòu)，也許是幾十K的規(guī)模。而在排序中我們頻繁地發(fā)生交換，經(jīng)常把東西挪來(lái)挪去，光挪動(dòng)的動(dòng)作會(huì)產(chǎn)生很大代價(jià)。所以提出一個(gè)問(wèn)題，對(duì)大結(jié)構(gòu)的所以提出一個(gè)問(wèn)題，對(duì)大結(jié)構(gòu)的對(duì)象排序，有沒(méi)有特殊的考慮？對(duì)象排序，有沒(méi)

6、有特殊的考慮？教學(xué)智慧捕捉教學(xué)智慧捕捉簡(jiǎn)要總結(jié)已學(xué)過(guò)簡(jiǎn)要總結(jié)已學(xué)過(guò)的兩種排序算法的兩種排序算法提出問(wèn)題提出問(wèn)題列，花色優(yōu)先，花色一樣的情況下數(shù)字優(yōu)先。給你一堆亂的撲克牌理，怎么理？?jī)煞N方法，一種是先按花色排成4堆，再按序列排好，放在一起；另外一種是按照每個(gè)數(shù)字一堆，接下來(lái)按照花色排好，接下來(lái)每一堆相同順序的排12345678這樣排好，一層一層弄。這樣的算法都是基數(shù)排序的方法。這里面有兩種策略，一種是優(yōu)先級(jí)高的先排；還有一種是優(yōu)先級(jí)低的先

7、排。問(wèn)題是對(duì)于整數(shù)，只有一個(gè)key，這種方法能用嗎？對(duì)，同樣可以。把整數(shù)的每一位作為不同的key，可以采用基數(shù)排序的方法進(jìn)行排序。演示使用基數(shù)排序?qū)φ麛?shù)排序的過(guò)程，優(yōu)先級(jí)低（個(gè)位數(shù)優(yōu)先級(jí)最低）的先排?；鶖?shù)排序的時(shí)間復(fù)雜度：n數(shù)據(jù)的最大位數(shù)（例：數(shù)據(jù)里最大的數(shù)是1234567，最大位數(shù)是7，復(fù)雜度為待排序的元素的個(gè)數(shù)n7）提出課后思考的問(wèn)題：按照key的優(yōu)先級(jí)從高到低和從低到高排序有什么區(qū)別。P5：章節(jié)總結(jié)：章節(jié)總結(jié)我們這個(gè)課程主要試講三

8、類數(shù)據(jù)結(jié)構(gòu)和兩類算法問(wèn)題，就是排序和查找。排序是計(jì)算機(jī)中最基礎(chǔ)的算法，應(yīng)用廣泛。簡(jiǎn)單排序：選擇排序、插入排序、冒泡排序。分別從上面三種簡(jiǎn)單算法的思路出發(fā)，引出以下算法：堆排序、希爾排序、快速排序。此外還有歸并排序、桶排序基數(shù)排序。使用排序算法需要考慮的問(wèn)題使用排序算法需要考慮的問(wèn)題：穩(wěn)定性、時(shí)間復(fù)雜度、空間復(fù)雜度。（對(duì)部分算法的時(shí)間、空間復(fù)雜度進(jìn)行了復(fù)習(xí)和總結(jié)）。第二部分：動(dòng)態(tài)查找第二部分：動(dòng)態(tài)查找P6：為什么要?jiǎng)討B(tài)查找：為什么要?jiǎng)討B(tài)查

9、找最簡(jiǎn)單的查找方法是就叫樸素查找，就是我給你一個(gè)集合，然后要到集合里去查找某個(gè)元素在不在。最簡(jiǎn)單的方法是把它們放在數(shù)組和列表里面，然后一個(gè)個(gè)去比較，第一個(gè)是不是，第二個(gè)是不是，但是這樣的時(shí)間復(fù)雜性是不太好的，平均是要到一半的時(shí)候才能找到。所以這個(gè)效率不高，一種辦法是從小到大排好，然后用二分法找。這就相當(dāng)于字典一樣，查單詞不是順序查找，從小到大按ABCD的順序排好，然后比較你要找的字母比看到的字母大還是小，根據(jù)大小分別到前后去找。二分查找

10、必須有兩個(gè)前提，第一數(shù)據(jù)必須按從小到大的順序排好，另外一個(gè)是必須放在數(shù)組里面，如果不放在數(shù)組（連續(xù)的空間）里面就沒(méi)辦法二分。那么這種查找的基本特點(diǎn)是什么？被找的集合是固定不變的。我們要面我們要面對(duì)的問(wèn)題是新的，被找的集合是動(dòng)態(tài)的。對(duì)的問(wèn)題是新的，被找的集合是動(dòng)態(tài)的。比如說(shuō)我們想往字典里加新的單詞，或者是有的單詞老是不用，我要把它刪掉。動(dòng)態(tài)查找的問(wèn)題把它歸納一下是：我要管理一個(gè)集合，經(jīng)常要往集合里面插入一個(gè)元素，刪除一個(gè)元素，找一個(gè)元素，

11、而靜態(tài)查找是只做一個(gè)操作，即find查找，那么這個(gè)時(shí)候可以用二分法做。如果這個(gè)集合不僅要做查找，還要做插入、刪除，那么就是動(dòng)態(tài)查找問(wèn)題。所以我們要相出新的方揭示了不同級(jí)別揭示了不同級(jí)別算法間的關(guān)系算法間的關(guān)系回顧用之前的方回顧用之前的方法如何解決查找法如何解決查找問(wèn)題：樸素查問(wèn)題：樸素查找、二分查找。找、二分查找。類比類比提出問(wèn)題提出問(wèn)題列舉需要使用動(dòng)列舉需要使用動(dòng)態(tài)查找算法的問(wèn)態(tài)查找算法的問(wèn)題小結(jié)：動(dòng)態(tài)查找小結(jié)：動(dòng)態(tài)查找需要維護(hù)一個(gè)集