【正文】 比較 3 次。 ++i ) input(b[i].key)。 while ( t 0 ) { if (b[s].key b[ls[t].key) s ls[t]。 k = 0。 1 0 0 存于 b[0] ~ b[k1]之中 初值： b[k] = ∞ 存于 ls[0] ~ ls[k1] 之中 3 5 33 物料管理 EXST 2/9/2023 33 Algorithms and DataStructures:EXSORT 置換 選擇排序 作用：產(chǎn)生盡可能長(zhǎng)的初始?xì)w并段。 書上介紹：該結(jié)論由： E ? 限制：由于磁帶尋找具有最少記錄的初始?xì)w并段，必須反復(fù)倒帶。如下例所示。 所以， K nk ＝ nk + m － 1 于是： nk ＝ ( m － 1 ) / ( K 1) 這就意味著，若 ( m － 1 ) MOD ( K 1) ＝ 0，無需增加虛段。在這棵樹上的結(jié)點(diǎn)要么 是葉子，要么是具有 K 個(gè)兒子的內(nèi)部結(jié)點(diǎn)。 :假定由置換－選擇分類法生成了 9 個(gè)初始?xì)w并段，記錄數(shù)分別為 1 1 1 24 。 程序?qū)崿F(xiàn)： 可以用敗者樹的辦法 加以實(shí)現(xiàn)。這 m 個(gè)記錄 肯定可以歸入本初始合并段內(nèi)。 1 k 0 存于 b[0] ~ b[k1]之中 初值： b[k] = ∞ 存于 ls[0] ~ ls[k1] 之中 3 29 物料管理 EXST 2/9/2023 29 Algorithms and DataStructures:EXSORT 2 k 多路平衡歸并的實(shí)現(xiàn) ? 敗者樹程序?qū)崿F(xiàn)： 7 29 5 9 3 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 3 2 1 0 2 1 輸 入 緩 沖 區(qū) 輸 出 緩 沖 區(qū) 注意：在輸出緩 沖區(qū)被寫滿之后 ，全部?jī)?nèi)容輸出 至帶或盤。 for ( i=0。 input(b[q].key)。 typedef struct { KeyType key。 21 物料管理 EXST 2/9/2023 21 Algorithms and DataStructures:EXSORT 多路平衡歸并的實(shí)現(xiàn) 勝者樹及其使用 ? 勝者進(jìn)入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的結(jié) 果，使得更快地挑出亞軍、第三名 …… 。 合并段 1 合并段 2 合并段 m1 合并段 m 中間合并段 中間合并段 中間合并段 中間合并段 有序文件 層數(shù)： log2m +1 歸并趟數(shù)： log2m 16 物料管理 EXST 2/9/2023 16 Algorithms and DataStructures:EXSORT 多路平衡歸并的實(shí)現(xiàn) 帶、盤的平衡多路歸并的性質(zhì)： ? : K 2 時(shí) , 趟數(shù)將會(huì)減少。六個(gè)初 始合并段均勻分布在 T T2 。這就要求在 內(nèi)存一定且進(jìn)行內(nèi)部排序時(shí)， 生成盡可能長(zhǎng)的歸并段，從而減少歸并段的 總數(shù)。 T T5 、 T6 初始為空。 2K = 6, 需 4條磁帶。對(duì)這 K 條帶進(jìn)行合并，將生成的中間歸并段分布在 TK+ TK+2 、 …… T 2K 上。 速度快、容量大、直接存取設(shè)備。 查找費(fèi)時(shí)、速度慢（尤其是查找末端記錄時(shí)）。 基本術(shù)語(yǔ)： 常用外存： ? 磁帶：由磁帶介質(zhì)、讀、寫磁頭、驅(qū)動(dòng)器、接收盤和原始盤組成。 ? 記錄（ Record）：數(shù)據(jù)項(xiàng)的集合存于內(nèi)存，稱之為結(jié)點(diǎn)。只能駐留在帶、盤、 CDROM 上。 ? 關(guān)鍵字：唯一標(biāo)識(shí)記錄的域，稱之為關(guān)鍵字。 查找費(fèi)時(shí)、速度慢。 tw 讀 /寫一個(gè)字符的時(shí)間； n 記錄數(shù)。 8 物料管理 EXST 2/9/2023 8 Algorithms and DataStructures:EXSORT 外部排序的方法 步驟： ? 生成合并段（ run）：讀入文件的部分記錄到內(nèi)存 － 在內(nèi)存中進(jìn)行內(nèi)部排序 － 將排好序的這些記錄寫入外存，形成合并段 － 再讀入該文件 的下面的記錄，往復(fù)進(jìn)行，直至文件中的記錄全部形成合并段 為止。每個(gè)合并段有 1000 個(gè)記錄。 2K = 6, 需 4條磁帶。 K 大，趟數(shù)減 少，讀寫記錄的總數(shù)將減少。 T T4 初始為空。 R（ 1…… 1000 ） R（ 2023…2023 ） R（ 4001... 5001） R（ 1001…… 2023 ） R（ 3001…4000 ） R（ 5001... 6000） T1 T2 T4： 空 T3 ： 空 250 個(gè)記錄 T1 T2 250 個(gè)記錄 250 個(gè)記錄 250 個(gè)記錄 250 個(gè)記錄 250 個(gè)記錄 250 個(gè)記錄 250 個(gè)記錄 IBG（ Inter Block Gap） 初始合并段 ( R（ 1…… 1000 ） ) 250 個(gè)記錄 T3 250 個(gè)記錄大 250 個(gè)記錄大 K(＝ 2)個(gè)輸入緩沖區(qū) 250 個(gè)記錄大 1個(gè)輸出緩沖區(qū) 讀入內(nèi)存 讀入內(nèi)存 15 物料管理 EXST 2/9/2023 15 Algorithms and DataStructures:EXSORT 多路平衡歸并的實(shí)現(xiàn) ? 時(shí)間分析 : logkm 趟 K 大，趟數(shù)減少，讀寫記錄的總數(shù)將減少。 每次比較耗費(fèi)的時(shí)間代價(jià)為 : tmg， 那么在進(jìn)行 k 平衡歸并時(shí)，總的時(shí)間耗費(fèi)不會(huì)超過： logkm ( k 1 ) ( n 1 ) tmg = log2m / log2k ( k 1 ) ( n 1 ) tmg k log2m / log2k ( k 1 ) 大 大 ? 改進(jìn)：采用勝者樹或者敗者樹，從 K 個(gè)元素中挑選一個(gè)最小的元素僅需 log2k 次比 較，這時(shí)總的時(shí)間耗費(fèi)將下降： logkm log2k ( n 1 ) tmg 勝者樹及其使用 勝者進(jìn)入下一輪，直至決出本次比賽的冠軍。 20 物料管理 EXST 2/9/2023 20 Algorithms and DataStructures:EXSORT 9 12 多路平衡歸并的實(shí)現(xiàn) 勝者樹及其使用 勝者進(jìn)入下一輪，直至決出本次比賽的冠軍。 5 0 0 5 23 物料管理 EXST 2/9/2023 23 Algorithms and DataStructures:EXSORT 29 16 多路平衡歸并的實(shí)現(xiàn) 7 29 16 9 9 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 7 6 5 4 3 2 1 輸 入 緩 沖 區(qū) 輸 出 緩 沖 區(qū) 5 7 注意：挑出亞軍 需要進(jìn)行 log2k 次比較，此處需 要比較 2 次。 CreateLoserTree(ls)。 t = t / 2。 i ) Adjust(ls,i)。在內(nèi)存長(zhǎng)度一定時(shí)，按照通常的排序方法，產(chǎn)生的 初始?xì)w并段的長(zhǎng)度只能和內(nèi)存長(zhǎng)度相同，但采用本方法之后可以產(chǎn)生卻可以生成 兩倍內(nèi)存長(zhǎng)度的初始?xì)w并段（平均情況下）。F所以，實(shí)用性不強(qiáng)。 55 物料管理 EXST 2/9/2023 55 Algorithms and DataStructures:EXSORT 最佳歸并樹 最佳歸并樹 ? 按照 HUFFMAN 樹的思想，記錄少的段最先合并。否則，要增加虛段，其 數(shù)目為： K－ 1－ ( m － 1 ) MOD ( K 1)。 ? 虛段的補(bǔ)法 : 解：在 K 路平衡歸并時(shí)，它的歸并樹的模型是一棵度為 K 的樹。文件如集中放置在幾個(gè)相 鄰的柱面上的情況比較合適。不過我認(rèn)為這種證明完全是胡扯。 34 物料管理 EXST 2/9/2023 34 Algorithms and DataStructures:EXSORT 置換 選擇排序 ? 實(shí)例的實(shí)現(xiàn)過程： F1： 3 2 1 1 2 4 1 3 1 2 29 在帶 1 上 步數(shù) 內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入） 輸出結(jié)果（至帶 F2 ） 1 3 2 19 19