【正文】 帶 F2 ） 1 3 2 19 19 2 3 2 (12) 21 3 3 2 (12) 26 4 3 4 (12) 31 5 (11)、 4 (12) 41 6 (11)、 (37)、 (12) 7 1 3 12 11 8 1 3 12 12 9 1 3 23 15 10 2 3 23 23 11 2 37 29 45 物料管理 EXST 2/9/2023 45 Algorithms and DataStructures:EXSORT 置換 選擇排序 ? 實(shí)例的實(shí)現(xiàn)過(guò)程： 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 2 3 2 (12) 21 3 3 2 (12) 26 4 3 4 (12) 31 5 (11)、 4 (12) 41 6 (11)、 (37)、 (12) 7 1 3 12 11 8 1 3 12 12 9 1 3 23 15 10 2 3 23 23 11 2 37 29 12 29 37 46 物料管理 EXST 2/9/2023 46 Algorithms and DataStructures:EXSORT 置換 選擇排序 ? 實(shí)例的實(shí)現(xiàn)過(guò)程： 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 2 3 2 (12) 21 3 3 2 (12) 26 4 3 4 (12) 31 5 (11)、 4 (12) 41 6 (11)、 (37)、 (12) 7 1 3 12 11 8 1 3 12 12 9 1 3 23 15 10 2 3 23 23 11 2 37 29 12 29 37 13 第二個(gè)初始合并段 47 物料管理 EXST 2/9/2023 47 Algorithms and DataStructures:EXSORT 置換 選擇排序 長(zhǎng)度分析： 設(shè)內(nèi)存可以存放 m 個(gè)記錄，則首先從文件讀入 m 記錄到內(nèi)存。這 m 個(gè)記錄 肯定可以歸入本初始合并段內(nèi)。這樣，必須從文件中讀入 m 個(gè)記錄。這 m 個(gè) 記錄中平均有一半可以歸入本合并段，一半歸入下一合并段。 因此，合并段的平均長(zhǎng)度為： m + m/2 + m/4 + ………… = 2m 所以，在平均情況下， 合并段的平均長(zhǎng)度為 2m 。 書上介紹：該結(jié)論由： EFMoore 在 1961 年從置換－選擇排序同掃雪機(jī)的類比中得到 的。不過(guò)我認(rèn)為這種證明完全是胡扯。 程序?qū)崿F(xiàn)： 可以用敗者樹(shù)的辦法 加以實(shí)現(xiàn)。 48 物料管理 EXST 2/9/2023 48 Algorithms and DataStructures:EXSORT 3 2 1 4 置換 選擇排序 敗者樹(shù)實(shí)現(xiàn)置換 選擇排序 5 2 29 0 1 0 5 4 3 4 3 2 1 6 15 46 1 39 1 49 1 51 1 29 1 38 1 5 4 3 49 物料管理 EXST 2/9/2023 49 Algorithms and DataStructures:EXSORT 3 2 0 4 置換 選擇排序 敗者樹(shù)實(shí)現(xiàn)置換 選擇排序 5 2 29 38 0 1 1 5 4 3 4 3 2 1 6 15 46 1 39 1 49 1 51 1 14 2 38 1 5 4 3 50 物料管理 EXST 2/9/2023 50 Algorithms and DataStructures:EXSORT 1 2 0 4 置換 選擇排序 敗者樹(shù)實(shí)現(xiàn)置換 選擇排序 5 2 29 38 39 0 1 3 5 4 3 4 3 2 1 6 15 46 1 39 1 49 1 51 1 14 2 61 1 5 4 3 51 物料管理 EXST 2/9/2023 51 Algorithms and DataStructures:EXSORT 1 2 0 4 置換 選擇排序 敗者樹(shù)實(shí)現(xiàn)置換 選擇排序 5 3 29 38 39 46 0 1 2 5 4 3 4 3 2 1 6 15 46 1 15 2 49 1 51 1 14 2 61 1 5 4 3 注意：在全部的 段號(hào)標(biāo)志變成 2 之后，合并段 1 的記錄已全部生 成。 ？ K 值越大越好嗎！ 52 物料管理 EXST 2/9/2023 52 Algorithms and DataStructures:EXSORT 最佳歸并樹(shù) 最佳歸并樹(shù) ? 起因：由于初始?xì)w并段通常不等長(zhǎng)。 ? 目的：減少讀寫外存的次數(shù)。 ? 限制：由于磁帶尋找具有最少記錄的初始?xì)w并段，必須反復(fù)倒帶。所以，實(shí)用性不強(qiáng)。在盤 的情況下，需要有段包含的記錄數(shù)信息、段的位置信息等。文件如集中放置在幾個(gè)相 鄰的柱面上的情況比較合適。 :假定由置換－選擇分類法生成了 9 個(gè)初始?xì)w并段，記錄數(shù)分別為 1 1 1 24 。如果進(jìn)行 3路歸并，請(qǐng)討論在各種情況下的對(duì)外存的讀寫次數(shù)。 30 12 9 3 17 18 6 24 2 51 38 32 121 從外存讀 121 個(gè)記錄 寫入外存 121 個(gè)記錄 從外存讀 121 個(gè)記錄 寫入外存 121 個(gè)記錄 A. 總共讀寫外存 484 個(gè)記錄 53 物料管理 EXST 2/9/2023 53 Algorithms and DataStructures:EXSORT 最佳歸并樹(shù) 最佳歸并樹(shù) 6 2 3 9 24 17 18 30 11 32 59 121 從外存讀 11 個(gè)記錄 寫入外存 11 個(gè)記錄 從外存讀 91個(gè)記錄 寫入外存 121 個(gè)記錄 B. 寫入外存 91 個(gè)記錄 從外存讀 121 個(gè)記錄 12 總共讀寫外存 446 個(gè)記錄 54 物料管理 EXST 2/9/2023 54 Algorithms and DataStructures:EXSORT 最佳歸并樹(shù) 最佳歸并樹(shù) 3 2 6 9 24 17 18 12 5 20 47 91 從外存讀 5 個(gè)記錄 寫入外存 5 個(gè)記錄 從外存讀 67 個(gè)記錄 寫入外存 91 個(gè)記錄 C. 寫入外存 67 個(gè)記錄 從外存讀 91 個(gè)記錄 總共讀寫外存 326 個(gè)記錄 ? 按照 HUFFMAN 樹(shù)的思想，記錄少的段最先合并。不夠時(shí)增加虛段。如下例所示。 55 物料管理 EXST 2/9/2023 55 Algorithms and DataStructures:EXSORT 最佳歸并樹(shù) 最佳歸并樹(shù) ? 按照 HUFFMAN 樹(shù)的思想，記錄少的段最先合并。不夠時(shí)增加虛段。 ? 虛段的補(bǔ)法 : 解：在 K 路平衡歸并時(shí)，它的歸并樹(shù)的模型是一棵度為 K 的樹(shù)。在這棵樹(shù)上的結(jié)點(diǎn)要么 是葉子，要么是具有 K 個(gè)兒子的內(nèi)部結(jié)點(diǎn)。設(shè)具有 K 個(gè)兒子的內(nèi)部結(jié)點(diǎn)共有 nk 個(gè) 。初始?xì)w并段的個(gè)數(shù)為 m 個(gè)。 設(shè) n = nk + m ， 故： 從結(jié)點(diǎn)出發(fā)的枝條，共計(jì)有： K nk 根 若從進(jìn)入結(jié)點(diǎn)結(jié)點(diǎn)的角度進(jìn)行考慮，則共有： nk + m － 1 注意：沒(méi)有枝條進(jìn)入根結(jié)點(diǎn)。 所以， K nk ＝ nk + m － 1 于是： nk ＝ ( m － 1 ) / ( K 1) 這就意味著，若 ( m － 1 ) MOD ( K 1) ＝ 0，無(wú)需增加虛段。否則，要增加虛段，其 數(shù)目為： K－ 1－ ( m － 1 ) MOD ( K 1)。 56 物料管理 EXST 2/9/2023 56 Algorithms and DataStructures:EXSORT 演講完畢，謝謝觀看！