【正文】 最佳情況下，兩個子表的長度相同，每個子表的長度最多是 n/2，因此 Topt(n)≤ + 2Topt(n/2) ≤ + 2(/2 + 2Topt(n/4) ≤2 + 4Topt(n/4) … ≤ log2n + nTopt(1) = O(n log n) JYP 29 （ 3）根據(jù)下面的引理 ，快速排序的平均時間復雜性也是 O(n log n)。兩個子表的長度為 j和 n–1–j，相應的平均時間是 Tavg(j) + Tavg(n–1–j)。假設對于 2≤n m， Tavg(n)≤knlogen。 JYP 35 ? 快速排序的最大遞歸深度是 n。 do j。 JYP 36 InterChange(list, left, j)。 right = j – 1。 在迭代歸并排序中，需要歸并的兩個表： ? (initListl, … , initList m) ? (initListm+1, … , initList n) 生成的結(jié)果表是 (mergedListl, … , mergedList n)。 i2 = n。 i2++。 else for (int t = i1。循環(huán)之外的 if語句總共最多移動 n–l+1個記錄。 ? 成對歸并這些表 ， 得到 n/2個已排序表 ， 每個表的長度為 2（ 如果 n是奇數(shù) ， 則最后一個表的長度為1） 。 如果 i≤n–2len， 則至少還有兩個長度都是 len的子表需要歸并 ， 否則需要作特殊邊界處理 。 i += 2len) merge(initList, resultList, i, i+len–1, i+2len–1)。 t++) resultList[t] = initList[t]。 l* = 2) { // l是當前被歸并子表的長度 MergePass(list, tempList, n, l)。 } JYP 47 對 MergeSort的分析： 對輸入表進行多次掃描。每遍掃描的時間為 O(n)。 ? 遞歸排序這些子表。 假設每個元素至少有兩個字段： link和 key，其結(jié)構定義如下： template class KeyType class Element { private: KeyType key。 // 1表示空指針 }。 JYP 52 函數(shù) ListMerge(list, start1, start2) 將兩個由 start1和 start2指向的按關鍵字非遞減次序鏈接的鏈表歸并為一個按關鍵字非遞減次序鏈接的鏈表 ， 并返回首記錄指針： template class KeyType int ListMerge(ElementKeyType *list, const int start1, const int start2) { // 將分別由 start1和 start2指向的已排序鏈表歸并為 // 一個已排序鏈表，并返回其首記錄的下標。 i1 = list[start1].link。 i1 = start1。 iResult = i1。 i2 = list[i2].link。 } JYP 54 函數(shù) rMergeSort利用 ListMerge實現(xiàn)遞歸歸并排序 ， 并返回已排好序鏈表的首記錄指針： template class KeyType int rMergeSort(ElementKeyType *list, const int left, const int right) { // 將 list[left], …, list[right] 按 key排序。 // 分別排序左、右半部分，并歸并所得的兩個已排序鏈表 return ListMerge(list, rMergeSort(list, left, mid), rMergeSort(list, mid+1, right))。 堆排序通過最大堆的插入和刪除操作實現(xiàn)排序： ? 首先將 n個記錄插入一個初始為空的堆， ? 接著逐個從堆中取出記錄。 int k = ( )。 // 較大者 if (k = tree[j].getKey( )) break。 JYP 57 算法 HeapSort首先利用函數(shù) adjust構建最大堆，如下圖所示： JYP 58 接著對記錄表 list作 n – 1遍處理，每次將當前最大堆的第一個記錄與最后一個交換，并將當前最大堆記錄數(shù)減少 1，重新調(diào)整。 i = 1。 i) { // 排序 list ElementKeyType t = list[i+1]。 // 重建堆 } } JYP 60 例 用 HeapSort對 (26, 5, 77, 1, 61, 11, 59, 15, 48, 19)的排序過程： JYP 61 JYP 62 JYP 63 JYP 64 JYP 65 分析： 設 2k–1≤n 2k，則與記錄表對應的完全二叉樹有 k層，第 i層的結(jié)點數(shù) ≤2i–1。 而且，只需要 O(1)輔助空間。 這里用關鍵字值來確定記錄在最終就序數(shù)組中的位置。 JYP 68 在實際應用中，一個箱子可以存放多個記錄，同時關鍵字的取值范圍不必與 n直接關聯(lián)。 我們按最低位優(yōu)先 （ 簡稱 LSD） 策略應用箱排序解決此問題： ? 首先根據(jù) K1將卡片逐張分配到 0號箱到 9號箱中 。 一般地，在 基數(shù)排序 中，用基數(shù) r分解關鍵字。 JYP 71 假設記錄表是 R0, …, R n1。 }。 i n–1。 // 鏈接成一個以 current開 // 頭的鏈表，用 1表示空指針 JYP 73 for (i = d – 1。 j++) f[j] = 1。 if (f[k] == 1) f[k] = current。 f[j] == 1。 for (int k = j+1。} list[last].link = 1。 // 返回已就序鏈表的第一個記錄下標 } JYP 74 分析： RadixSort對數(shù)據(jù)作 d遍掃描，每遍掃描用O(n+r) 時間，總計算時間是 O(d(n+r))。 JYP 75 JYP 76 JYP 77 JYP 78 實驗作業(yè)： P260—25 JYP 79 外排序 概述 需要排序的記錄表大到計算機內(nèi)存不能容納時，內(nèi)排序已不足以解決問題。一個 IO塊通?？砂鄠€記錄。 其中，就數(shù)據(jù)傳輸而言，尋找和等待都是輔助性的，但其時間卻較長。 （ 2） 歸并第一階段生成的歸并段 ， 直到最終只剩一個歸并段 。 例 ，生成初始歸并段需要 1遍數(shù)據(jù)掃描， 歸并需要 遍數(shù)據(jù)掃描。例如，如果在上例中采用 6路歸并，則只需對數(shù)據(jù)掃描一遍即可完成排序。 下面將分別討論這些問題。因此 ， 當 k 2時 ， 采用 k路歸并可有效減少輸入輸出時間 。 歸并 logkm遍的 CPU處理時間是 O(n log2k logkm) = O(n log2m)， 即與 k無關 。 k值的最佳選擇與磁盤參數(shù)和可用于緩沖區(qū)的內(nèi)存容量有關。 JYP 92 設內(nèi)存可容納 k個記錄，用 r[0], r[1], …, r[k –1]表示，記錄的輸入和輸出通過 IO緩沖實現(xiàn)。 JYP 93 將內(nèi)存記錄所屬的歸并段號作為第一子關鍵字，記錄原來的關鍵字作為第二子關鍵字，下一個要輸出的記錄是 k個記錄中關鍵字最小的。 ? rc存放當前歸并段號。 ? 當輸入記錄表已讀空時，我們可以構造歸并段號為 rmax + 1的虛擬記錄，以將敗者樹中的實際記錄“頂”出。 5 for ( int i = 0。 7 } 8 InitializeLoserTree(r, l, rn, k)。 int rmax = 1。 // 遇到虛擬記錄，說明實際 // 記錄已輸出完，跳出循環(huán) 15 else rc = rq。 // 生成虛擬記錄，以把實 // 際記錄“頂”出敗者樹 20 else { 21 ReadRecord (r[q])。 26 // 重新調(diào)整敗者樹 27 for (int t = (k + q)/2。 r[l[t]].key r[q].key)) { // t是勝者 29 int temp = q。 31 } 32 } // while循環(huán)結(jié)束 33 delete [ ] r。平均而言， runs生成的歸并段長度是傳統(tǒng)方法的兩倍。 JYP 108 例如 ， 假設有四個歸并段 ， 長度分別為 3， 4， 8和21。 前面兩棵樹的加權外部路徑長度分別是 3?3 + 4?3 + 8?2 + 21?1 = 58 和 3?2 + 4?2 + 8?2 + 21?2 = 72。 設需要建立信息 M1, M2, …, M n 的一組最佳編碼。信息編碼字中的二進制位決定了到達正確外部結(jié)點需經(jīng)過的各層分枝。 JYP 113 哈夫曼給出了建立具有最短加權外部路徑長度的二叉樹的有效方法 ， 因此這種樹又稱為 哈夫曼樹 。 BinaryTreeNode *RightChild。 root?RightChild = 。 JYP 115 函數(shù) huffman利用一個由擴展二叉樹構成的表 list。 i++) { // 循環(huán) n1次，以結(jié)合 n個結(jié)點 BinaryTree first = ( )。 } } 其中用到函數(shù) List::DeleteMinWeight( )，List::Size( )和 List::Insert( )。將表 list維護為一個最小堆，每次調(diào)用 DeleteMinWeight和 Insert只需要O(log n)時間，總計算時間是 O(n log n)。本章學習各種有效實現(xiàn)符號表的查找結(jié)構。 JYP 123 符號表的操作： （ 1） 確定一個給定的名字是否在表中 （ 2） 獲取與該名字對應的屬性 （ 3） 修改與該名字對應的屬性 （ 4） 插入一個新的名字及其屬性 （ 5） 刪除一個名字及其屬性 JYP 124 符號表的抽象數(shù)據(jù)類型定義： template class Name, Attribute class SymbolTable { // 對象 : 名字 —屬性對集合，其中每個名字都是唯一的 public: SymbolTable(int size = DefaultSize)。 // 如果 name在符號表 // 中，則用 attr替換原有屬性，否 // 則將 (name, attr)插入符號表中 JYP 125 void Delete(Name name)。 在實際應用中，又常常將符號表作為元素集合，元素的 key字段表示名字或關鍵字，其它字段表示屬性。 JYP 128 二叉查找樹的查找、插入和刪除操作 1 查找 假設需要查找關鍵字為 k的元素 ， 根據(jù)二叉查找樹的性質(zhì) ， 很容易得到其查找方法： ? 查找從樹根開始 。 ? 如果 k小于樹根中元素的關鍵字則只需查找左子樹否則只需查找右子樹 。 if (k t?) t = t?LeftChild。 data至少含類型為 Type的字段 key。 if (k t? LeftSize) t = t?LeftChild。 } JYP 131 假設二叉查找樹的高度為 h，則無論是按關鍵字查找還是按位次查找，在最壞情況下算法的計算時間為 O(h)。該查找不成功，且最后一個檢查的是結(jié)點 40。 BstNodeType*q = 0。 else p = p?RightChild。 if (!root) root = p。 } 設 h是查找樹的高度 ， 則插入的計算時間是 O(h) 。 ? 刪除只有一個子女的非葉結(jié)點中的元素只需將含該元素的結(jié)點釋放，并用其唯一子女取代被釋放結(jié)點的位置即可。可釋放結(jié)點 5 ，并使結(jié)點 2成為結(jié)點 30的新的左子女。