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

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

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

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

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

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

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

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

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

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

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

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