【正文】 當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆 或 (i=1,2,…... ?n/2?) ki?k2i ki?k2i+1 ki?k2i ki?k2i+1 例 （ 96， 83， 27， 38， 11， 9） 例 （ 13， 38， 27， 50， 76， 65， 49， 97） 96 27 9 11 38 83 13 27 38 49 65 76 50 97 可將堆序列看成完全二叉樹(shù)，則堆頂 元素（完全二叉樹(shù)的根）必為序列中 n個(gè)元素的最小值或最大值 ? 堆排序：將無(wú)序序列建成一個(gè)堆，得到關(guān)鍵字最小（或最大）的記錄；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余?n1個(gè)元素重又建成一個(gè)堆，則可得到 n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列，這個(gè)過(guò)程叫 ~ ? 堆排序需解決的兩個(gè)問(wèn)題： ? 如何由一個(gè)無(wú)序序列建成一個(gè)堆？ ? 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？ ? 第二個(gè)問(wèn)題解決方法 —— 篩選 ? 方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“篩選” 例 13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 輸出： 13 27 49 38 97 65 76 50 13 輸出： 13 97 49 38 27 65 76 50 13 輸出： 13 27 38 49 50 27 65 76 97 13 輸出： 13 27 65 49 50 27 38 76 97 13 輸出： 13 27 38 49 65 50 27 38 76 97 13 輸出： 13 27 38 76 65 50 27 38 49 97 13 輸出： 13 27 38 49 50 65 76 27 38 49 97 13 輸出： 13 27 38 49 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 97 76 27 38 49 50 13 輸出： 13 27 38 49 50 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 76 65 97 27 38 49 50 13 輸出： 13 27 38 49 50 65 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 76 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 76 97 ? 算法描述 ? 第一個(gè)問(wèn)題解決方法 ? 方法：從無(wú)序序列的第 ?n/2?個(gè)元素（即此無(wú)序序列對(duì)應(yīng)的完全二叉樹(shù)的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選 例 含 8個(gè)元素的無(wú)序序列（ 49， 38， 65， 97， 76， 13， 27， 50） 49 65 38 27 13 76 97 50 49 65 38 27 13 76 50 97 49 13 38 27 65 76 50 97 49 13 38 27 65 76 50 97 13 27 38 49 65 76 50 97 P281 圖 ? 算法描述 ? 算法評(píng)價(jià) ? 時(shí)間復(fù)雜度：最壞情況下 T(n)=O(nlogn) ? 空間復(fù)雜度： S(n)=O(1) ? 歸并排序 ? 歸并 —— 將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表，叫 ~ ? 2路歸并排序 ? 排序過(guò)程 ? 設(shè)初始序列含有 n個(gè)記錄，則可看成 n個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為 1 ? 兩兩合并，得到 ?n/2?個(gè)長(zhǎng)度為 2或 1的有序子序列 ? 再兩兩合并， …… 如此重復(fù)，直至得到一個(gè)長(zhǎng)度為 n的有序序列為止 例 初始關(guān)鍵字： [49] [38] [65] [97] [76] [13] [27] 一趟歸并后： [38 49] [65 97] [13 76] [27] 二趟歸并后： [38 49 65 97] [13 27 76] 三趟歸并后： [13 27 38 49 65 76 97] ? 算法描述 ? 算法評(píng)價(jià) ? 時(shí)間復(fù)雜度： T(n)=O(nlog2n) ? 空間復(fù)雜度： S(n)=O(n) ? 基數(shù)排序 ? 鏈?zhǔn)交鶖?shù)排序 ? 基數(shù)排序：借助“分配”和“收集”對(duì)單邏輯關(guān)鍵字進(jìn)行排序的一種方法 ? 鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序 P284 而實(shí)現(xiàn) 基數(shù)排序不需要進(jìn)行記錄關(guān)鍵字間的比較 例 初始狀態(tài)： 278 109 063 930 589 184 505 269 008 083 109 589 269 278 063 930 083 184 505 008 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 一趟分配 930 063 083 184 505 278 008 109 589 269 一趟收集： 505 008 109 930 063 269 278 083 184 589 二趟收集： 083 184 589 063 505 269 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配 008 109 278 930 063 083 184 505 278 008 109 589 269 一趟收集： 008 063 083 109 184 269 278 505 589 930 三趟收集： 109 008 184 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配 063 083 269 278 505 589 505 008 109 930 063 269 278 083 184 589 二趟收集： ? 算法描述 ? 算法評(píng)價(jià) ? 時(shí)間復(fù)雜度： ? 分配： T(n)=O(n) ? 收集： T(n)=O(rd) T(n)=O(d(n+rd)) 其中： n—— 記錄數(shù) rd—— 關(guān)鍵字取值范圍 d—— 關(guān)鍵字?jǐn)?shù) (分配收集的趟數(shù) ) ? 空間復(fù)雜度： S(n)=2rd個(gè)隊(duì)列指針 +n個(gè)指針域空間 ￡ 各種內(nèi)部排序方法的比較討論 （ 1）算法比較 綜合比較本章內(nèi)討論的各種內(nèi)部排序方法，大致有如下結(jié)果： 基數(shù)排序 O(d(n+rd)) O(d(n+rd)) O(rd) 排序方法 平均時(shí)間 最壞情況 輔助存儲(chǔ) 簡(jiǎn)單排序 O(n2) O(n2) O(1) 快速排序 O(nlogn) O(n2) O(nlogn) 堆排序 O(nlogn) O(nlogn) O(1) 歸并排序 O(nlogn) O(nlogn) O(n) 從上表易知，本章討論的所有排序方法中，沒(méi)有哪一種是絕對(duì)最優(yōu)的。 圖 (a)中的二叉樹(shù)表示從 8個(gè)關(guān)鍵字中選出最小關(guān)鍵字的過(guò)程。 ￡ 選擇排序 選擇排序（ Selection Sort）的基本思想是：每一趟 ni+1(i = 1, 2, … , n 1) 個(gè)記錄中選取關(guān)鍵字 最小 的記錄作為有序序列中第 i個(gè)記錄 ￡ 簡(jiǎn)單選擇排序 （ 1）算法實(shí)現(xiàn)： 一趟簡(jiǎn)單選擇排序的操作為：通過(guò) ni次關(guān)鍵字間的比較，從 ni+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第 i（ 1≤i≤n）個(gè)記錄交換之。 ① 主要思想 通過(guò)一趟排序?qū)⒋判蛴涗?分割成獨(dú)立的兩部分 ， 其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小， 則可 分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序 ，以達(dá)到整個(gè)序列有序。 （ 4）特點(diǎn) 希爾排序的特點(diǎn)是：子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。 //表結(jié)點(diǎn)類型 typedef struct { SLNode r[SIZE]。 ???nii2)1(② 當(dāng)待排序列中記錄按關(guān)鍵字非遞增有序排序（“逆序”）時(shí)，總的比較次 ??ni i2③ 若待排序記錄是隨機(jī)的，約為 n2/4。 外部排序 ：指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄， 在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。,2178。 移位疊加 ：將分割后的每一部分的最低位對(duì)齊，然后相加。 2．例子 假設(shè) BASIC語(yǔ)言中允許的標(biāo)識(shí)符為一個(gè)字母，或一個(gè)字母和一個(gè)數(shù)字。 地址 01 02 03 … 22 … 年份 1949 1950 1951 … 1970 … 人數(shù) … … … … 15000 … 其中，關(guān)鍵字是年份，哈希函數(shù)取關(guān)鍵字加一常數(shù)： H(key) = key + (－ 1948)。 ￡ 哈希表 ￡ 定義 哈希 （ Hash）函數(shù)：在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立的一個(gè)確定的對(duì)應(yīng)關(guān)系 f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。 45 24 53 12 90 45 24 53 12 45 24 53 45 24 45 (a) (b) (c) (d) (e) (f) 圖 二叉排序樹(shù)的構(gòu)造過(guò)程 二叉排序樹(shù)查找的性能分析 在二叉排序樹(shù)查找中 ， 成功的查找次數(shù)不會(huì)超過(guò)二叉樹(shù)的深度 ， 而具有 n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的深度 ， 最好為log2n， 最壞為 n。 s－ lchild = s－ rchild = NULL。 return FALSE。 else if (LT(key, T－ )) //在左子樹(shù)中繼續(xù)查找 return (SearchBST (T－ lchild, key))。 分塊查找的 算法思想 ： ① 確定待查記錄所在的塊（子表）； ② 在塊中順序查找 （ 2）性能分析 分塊查找的平均查找長(zhǎng)度為： 其中： Lb為查找索引表確定所在塊的平均查找長(zhǎng)度， Lw為在塊中查找元素的 平均查找長(zhǎng)度。 ? ? 1log 2 ?n 例如，上述 11個(gè)元素的表的例子。 else if (LT(key, [mid].key)) //繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 high = mid－ 1。它對(duì)表的結(jié)構(gòu)無(wú)任何要求，無(wú)論 記錄是否按關(guān)鍵字有序均可應(yīng)用。 !EQ([i].key, key)。 對(duì)于含有 n個(gè)記錄的表，查找成功時(shí)的平均查找長(zhǎng)度為： ??? niiiCPA SL1（ 9－ 1） 其中： Pi為查找表中查找第 i個(gè)記錄的概率，且 ???ni iP11 ； Ci為