【文章內(nèi)容簡(jiǎn)介】 作業(yè)： P259—13 JYP 48 遞歸 歸并 排序 * 遞歸歸并排序的基本思想： ? 將記錄表劃分成大致等長(zhǎng)的左、右子表。 ? 遞歸排序這些子表。 ? 再歸并已排序的子表，從而使整個(gè)記錄表就序。 JYP 49 例 對(duì)輸入表 (26, 5, 77, 61, 11, 59, 15, 48, 19) 進(jìn)行遞歸歸并排序過(guò)程中的子表劃分： JYP 50 將子表從一個(gè)數(shù)組歸并到另一個(gè)數(shù)組需要復(fù)制數(shù)據(jù)。采用鏈表表示可避免數(shù)據(jù)復(fù)制。 假設(shè)每個(gè)元素至少有兩個(gè)字段： link和 key，其結(jié)構(gòu)定義如下： template class KeyType class Element { private: KeyType key。 // 關(guān)鍵字 int link。 // 其它字段 public: Element( ) {link = 1。}。 // 1表示空指針 }。 JYP 51 假設(shè)： ? 所有訪問(wèn) Element私有數(shù)據(jù)成員的的函數(shù)已聲明為Element的友元 。 ? list[i].key和 list[i].link分別是記錄 i的 key和 link字段的值 （ 0≤i≤n–1） 。 ? 初始時(shí) list[i].link = –1（ 0≤i≤n–1） ， 即每個(gè)記錄構(gòu)成一個(gè)只含其本身的鏈表 。 JYP 52 函數(shù) ListMerge(list, start1, start2) 將兩個(gè)由 start1和 start2指向的按關(guān)鍵字非遞減次序鏈接的鏈表歸并為一個(gè)按關(guān)鍵字非遞減次序鏈接的鏈表 ， 并返回首記錄指針： template class KeyType int ListMerge(ElementKeyType *list, const int start1, const int start2) { // 將分別由 start1和 start2指向的已排序鏈表歸并為 // 一個(gè)已排序鏈表，并返回其首記錄的下標(biāo)。記錄 // 之間通過(guò)整型下標(biāo)鏈接。 int iResult, iStart, i1, i2。 if (list[start1].key = list[start2].key) { // 定位結(jié)果表的首記錄 iStart = iResult = start1。 i1 = list[start1].link。 i2 = start2。 } JYP 53 else { iStart = iResult = start2。 i2 = list[start2].link。 i1 = start1。 } while (i1 1 amp。amp。 i2 1) // 歸并 if (list[i1].key = list[i2].key) { list[iResult].link = i1。 iResult = i1。 i1 = list[i1].link。 } else { list[iResult].link = i2。 iResult = i2。 i2 = list[i2].link。 } if (i1== 1) list[iResult].link = i2。 // 鏈接剩余部分 else list[iResult].link = i1。 return iStart。 } JYP 54 函數(shù) rMergeSort利用 ListMerge實(shí)現(xiàn)遞歸歸并排序 ， 并返回已排好序鏈表的首記錄指針： template class KeyType int rMergeSort(ElementKeyType *list, const int left, const int right) { // 將 list[left], …, list[right] 按 key排序。返回已 // 排序鏈表的首記錄下標(biāo)。 if (left = right) return left。 // 最多只含一個(gè)記錄 int mid = (left + right)/2。 // 分別排序左、右半部分，并歸并所得的兩個(gè)已排序鏈表 return ListMerge(list, rMergeSort(list, left, mid), rMergeSort(list, mid+1, right))。 } 當(dāng)需要對(duì) list[0], … , list[n–1]排序時(shí) ， 可調(diào)用rMergeSort(list, 0, n–1)。 此排序也是穩(wěn)定的 。 JYP 55 堆 排序 堆排序只需要 O(1)的輔助空間，同時(shí)其最壞和平均時(shí)間復(fù)雜性也都是 O(n log n)。 堆排序通過(guò)最大堆的插入和刪除操作實(shí)現(xiàn)排序： ? 首先將 n個(gè)記錄插入一個(gè)初始為空的堆， ? 接著逐個(gè)從堆中取出記錄。 然而，還可以通過(guò)函數(shù) adjust更快地構(gòu)建具有 n個(gè)記錄的堆。 給定一棵二叉樹(shù) T，其左、右子樹(shù)都滿足最大堆的性質(zhì)，但其根結(jié)點(diǎn)卻不一定滿足，函數(shù) adjust調(diào)整 T使得整個(gè)二叉樹(shù)都滿足最大堆性質(zhì)。 JYP 56 template class KeyType void adjust (ElementKeyType *tree, const int root, const int n) { // 結(jié)點(diǎn)下標(biāo)不大于 n ElementKeyType e = tree[root]。 int k = ( )。 for (int j = 2*root。 j = n。 j *= 2) { if (j n) // j一定有右兄弟 if (tree[j].getKey( ) tree[j+1].getKey( )) j++。 // 較大者 if (k = tree[j].getKey( )) break。 // 如果 k不小于左、右子女 // 中的較大者，則 e可放在 j的雙親處 tree[j/2] = tree[j]。 // 將第 j個(gè)記錄上移 } tree[j/2] = e。 } 設(shè)以 root為根的樹(shù)深為 d，其計(jì)算時(shí)間為 O(d)。 JYP 57 算法 HeapSort首先利用函數(shù) adjust構(gòu)建最大堆，如下圖所示： JYP 58 接著對(duì)記錄表 list作 n – 1遍處理，每次將當(dāng)前最大堆的第一個(gè)記錄與最后一個(gè)交換，并將當(dāng)前最大堆記錄數(shù)減少 1，重新調(diào)整。 由于第一個(gè)記錄的關(guān)鍵字總是堆中最大的，經(jīng)過(guò)交換該記錄一定是就序的。 調(diào)用 HeapSort(list, n)即可對(duì) list[1], …, list[n] 排序。 JYP 59 template class KeyType void HeapSort (ElementKeyType *list, const int n) { // 按關(guān) // 鍵字非遞減次序排序 list[1], …, list[n] for (int i = n /2。 i = 1。 i) // 將 list轉(zhuǎn)化為最大堆 adjust(list, i, n)。 for (i = n – 1。 i = 1。 i) { // 排序 list ElementKeyType t = list[i+1]。 list[i+1] = list[1]。 list[1] = t。 // 交換 list[1]和 list[i+1] adjust(list, 1, i)。 // 重建堆 } } JYP 60 例 用 HeapSort對(duì) (26, 5, 77, 1, 61, 11, 59, 15, 48, 19)的排序過(guò)程： JYP 61 JYP 62 JYP 63 JYP 64 JYP 65 分析： 設(shè) 2k–1≤n 2k，則與記錄表對(duì)應(yīng)的完全二叉樹(shù)有 k層，第 i層的結(jié)點(diǎn)數(shù) ≤2i–1。第一個(gè) for循環(huán)對(duì)每個(gè)有子女的結(jié)點(diǎn)調(diào)用 adjust一次。該循環(huán)的時(shí)間不大于各層結(jié)點(diǎn)數(shù)與該層結(jié)點(diǎn)可移動(dòng)的最大距離的積之和，即 第二個(gè) for循環(huán)調(diào)用 adjust共 n–1次，最大深度為 ?log2(n+1)?。 因此，堆排序的總計(jì)算時(shí)間是 O(n log n)。 而且，只需要 O(1)輔助空間。 )(22/2/22)(211111111111 nOniniiikkiiikikkiikkii ?????? ????????????????????JYP 66 作業(yè)： P259—16 JYP 67 基數(shù) 排序 當(dāng) n個(gè)記錄的關(guān)鍵字 list[i].key（ 0≤in）的取值是0到 n–1范圍內(nèi)的整數(shù)時(shí)，可以用下列代碼對(duì)其排序： for (int i = 0。 i n。 i++) result[list[i].key] = list[i]。 這里用關(guān)鍵字值來(lái)確定記錄在最終就序數(shù)組中的位置。這就是最基本的 箱排序 。 其中，我們?yōu)?n個(gè)關(guān)鍵字值安排 n個(gè)箱子，并根據(jù)關(guān)鍵字值將記錄分配到對(duì)應(yīng)的箱中。 此方法效率極高，無(wú)論記錄關(guān)鍵字的初始順序如何，只需要 O(n) 時(shí)間即可完成排序。 JYP 68 在實(shí)際應(yīng)用中，一個(gè)箱子可以存放多個(gè)記錄，同時(shí)關(guān)鍵字的取值范圍不必與 n直接關(guān)聯(lián)。 為了有效地利用箱排序的思想，可以將關(guān)鍵字解釋為多個(gè)子關(guān)鍵字： K0, …, K d–1（ K0是最高位，Kd–1是最低位）。 如果記錄表 R0, …, R n1中的任意兩個(gè)記錄 Ri和 Rj（ 0≤i j n）都滿足 則稱該記錄表相對(duì)于關(guān)鍵字 (K0, …, K d–1) 已排好序。 ),.. .,(),.. .,( 1010 ?? ? djjdii KKKKJYP 69 例如 ， 排序 100張關(guān)鍵字值為 0到 99的卡片可看成對(duì)兩個(gè)子關(guān)鍵字 K0和 K1的排序 ， 其中 K0對(duì)應(yīng)十位 ，K1對(duì)應(yīng)個(gè)位 。 我們按最低位優(yōu)先 （ 簡(jiǎn)稱 LSD） 策略應(yīng)用箱排序解決此問(wèn)題： ? 首先根據(jù) K1將卡片逐張分配到 0號(hào)箱到 9號(hào)箱中 。 ? 接著 ， 將 8號(hào)箱的卡片放在 9號(hào)箱的之前 ， … ， 將 0號(hào)箱的卡片放在 1號(hào)箱的之前 。 ? 再根據(jù) K0按照穩(wěn)定排序的要求將卡片逐張分配到 0號(hào)箱到 9號(hào)箱中 ， 按照從 0到 9的箱號(hào)順序收集即得到已排序的卡片 。 JYP 70 可見(jiàn)，如果關(guān)鍵字是十進(jìn)制數(shù)，可將其中的每個(gè)十進(jìn)制位看成一個(gè)子關(guān)鍵字，并按 LSD策略用 10個(gè)箱子對(duì)每個(gè)子關(guān)鍵字進(jìn)行箱排序。 一般地，在 基數(shù)排序 中，用基數(shù) r分解關(guān)鍵字。 當(dāng) r = 10，則得到上述十進(jìn)制分解。 如果關(guān)鍵字是長(zhǎng)度為 d的小寫英文標(biāo)識(shí)符，則可分解為 d個(gè)子關(guān)鍵字 (K0, …, K d–1)，其中， Ki ? {‘a(chǎn)’, ‘b’, …, ‘z’} （ 0≤i d）， r = 26。 基數(shù) r排序需要 r個(gè)箱子。 JYP 71 假設(shè)記錄表是 R0, …, R n1。關(guān)鍵字用基數(shù) r分解，每個(gè)分解為 d位，每位的取值是 0到 r – 1，則需要 r個(gè)箱子。 記錄元素的類定義如下： class Element { public: … private: int key[d]。 // 關(guān)鍵字?jǐn)?shù)組， d是常數(shù) // 其它字段 … int link。 }。 JYP 72 每個(gè)箱子中的記錄鏈接成隊(duì)列 ， f[i]和 e[i]（ 0≤i r） 分別指向第 i個(gè)箱子的首 、 尾記錄 。 函數(shù) RadixSort給出了用 LSD策略實(shí)現(xiàn)基數(shù) r排序的細(xì)節(jié)： int RadixSort (Element *list, const int d, const int n) { // 按關(guān)鍵字 key[0],…key[d 1]排序 (list[0],…,list[n 1])， // 0≤key[i] radix， radix是常數(shù) int f[radix], e[radix]。 // radix個(gè)隊(duì)列的首、尾指針 for (int i = 0。 i n–1。 i++) lis