算法與數(shù)據(jù)結(jié)構(gòu)課件-DSC11

第十一章.外部排序（Chapter11.ExternalSorting)待排序列記錄數(shù)量太大，不能全部存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中，排序過程中需對(duì)計(jì)算機(jī)外存進(jìn)行訪問，這種排序過程稱為外部排序?！?1.1外存信息的存取一、磁帶信息的存?。?/p>

磁帶是在一條塑料薄膜上涂有磁性材料用以記錄數(shù)據(jù)的存儲(chǔ)介質(zhì)。其記錄組之間有一定的空隙IRG（InterRecordGap），它不是連續(xù)運(yùn)轉(zhuǎn)的設(shè)備，讀寫二、磁盤信息的存?。?/p>

磁盤是在一片塑料薄膜上涂有磁性材料用以記錄數(shù)據(jù)的存儲(chǔ)介質(zhì)。它分成多個(gè)磁道（柱面），每個(gè)磁道又分為多個(gè)扇區(qū)，多個(gè)磁盤組成的磁盤組還涉及到盤片號(hào)（磁頭號(hào)），磁盤繞軸高速旋轉(zhuǎn)，讀寫頭則沿其一條半徑作直線運(yùn)動(dòng)以尋道。它也不是信息只能在運(yùn)行穩(wěn)定時(shí)進(jìn)行，且找到要讀寫的記錄也需要一定的繞帶時(shí)間，因此，在磁帶上讀寫信息所需的時(shí)間由兩部分組成：TI/O=td+ntw，其中td

為延遲時(shí)間，即讀寫磁頭到達(dá)信息所在物理塊起始位置所需時(shí)間，tw

為傳輸一個(gè)記錄的時(shí)間。磁帶是一種順序存儲(chǔ)設(shè)備。§11.2外部排序的方法

總體要用歸并排序，亦即將待排序列分成若干子序列分別進(jìn)入內(nèi)存排成有序序列（初始?xì)w并段），再用歸并排序?qū)⑺袣w并段排序成一個(gè)有序序列。連續(xù)運(yùn)轉(zhuǎn)的設(shè)備，讀寫信息只能在旋轉(zhuǎn)穩(wěn)定時(shí)進(jìn)行，且找到要讀寫的記錄也需要一定的尋道、尋扇區(qū)時(shí)間，因此，在磁盤上讀寫信息所需的時(shí)間由三部分組成：TI/O=tseek+tla+ntw，其中tseek

為尋道時(shí)間（seektime），tla

為尋扇區(qū)時(shí)間（latencytimetime），tw

為傳輸時(shí)間（transmissiontime）。磁盤是一種隨機(jī)存儲(chǔ)設(shè)備。

一般情況下，外部排序所需的總時(shí)間由三部分構(gòu)成：內(nèi)部排序（產(chǎn)生初始?xì)w并段）所需時(shí)間（m*tIS

）、外存信息讀寫時(shí)間（d*tIO

）、內(nèi)部歸并所需時(shí)間（s*utmg

）。其中tIS

是為得到一個(gè)初始?xì)w并段進(jìn)行內(nèi)部排序所序的平均時(shí)間，tIO

是進(jìn)行一次外存讀寫的平均時(shí)間，utmg

是對(duì)u個(gè)記錄進(jìn)行內(nèi)部歸并所需的時(shí)間，m為初始?xì)w并段的個(gè)數(shù)，s為歸并的趟數(shù)，d為總的讀寫次數(shù)。但由于訪問外存儲(chǔ)器的時(shí)間開銷太大，即tIO

遠(yuǎn)遠(yuǎn)大于tmg，因此，要提高外部排序速度，就必須減少訪問外存的次數(shù)。

對(duì)同一待排序列而言，外部排序訪問外存的總次數(shù)d與歸并的趟數(shù)s成正比，而對(duì)m

個(gè)初始?xì)w并段進(jìn)行k路平衡歸并所需的趟數(shù)s=logkm，因此，增加k或減少m均能減少s。

利用敗者樹（treeofloser）可解決這一問題：類似于錦標(biāo)賽排序的思想，在進(jìn)行k路平衡歸并時(shí)，將相互比較過的關(guān)鍵字值較大的初始?xì)w并段號(hào)（敗者）留在樹結(jié)點(diǎn)中，將關(guān)鍵字值較小的初始?xì)w并段號(hào)（勝者）上傳，直到找到最終的勝者（最小值的段號(hào)）；將其歸并后，其下一記錄將替換它參加新的一輪比賽以找到新的最小值段號(hào)；反復(fù)此過程，直至全部k個(gè)初始?xì)w并段合并成一個(gè)有序序列為止。此時(shí)的歸并時(shí)間為log2m(n-1)tmg，與k無關(guān)，但k也并非越大越好?！?1.3多路平衡歸并的實(shí)現(xiàn)若單純?cè)黾觡以減少s，將會(huì)增加內(nèi)部歸并的時(shí)間utmg

，這將抵銷d隨s減少而得到的效益，如何解決這一矛盾呢？516128305233416283112141781015303856b3b4b0b1b2[0][1][2][3][4]

初始?xì)w并段

0b55555516045165033002830801125058135232334482316316124128018101015291030210120110151529885-路平衡歸并的敗者樹：

例：§11.4置換-選擇排序…

利用置換-選擇排序（replacement-selectionsort）可以達(dá)到這個(gè)目的（也用敗者樹實(shí)現(xiàn)）：

置換-選擇排序是在選擇排序的基礎(chǔ)上，當(dāng)最小關(guān)鍵字記錄被選出后，它空出的位置補(bǔ)充進(jìn)一個(gè)新的記錄，以后再求最小記錄時(shí)，不能選擇比剛才的最小記錄關(guān)鍵字小的記錄，只能從大于它的記錄中尋找新的最小關(guān)鍵字記錄。反復(fù)此過程，直至工作區(qū)中所有記錄的關(guān)鍵字均比剛出去的最小記錄的關(guān)鍵字小為止，此時(shí)得到的就是一個(gè)完整的初始?xì)w并段。

除了增加k可以減小s外，減小m也是減小s的另一有效途徑。但減小m就意味著要增加初始?xì)w并段長(zhǎng)度，這又受到計(jì)算機(jī)內(nèi)存大小的制約，又該如何解決這個(gè)問題呢？設(shè)計(jì)算機(jī)工作區(qū)大小為W=5，試給出下面待排序列利用置換-選擇排序得到的初始?xì)w并段：{23,45,12,5,2,6,27,39,16,44,55,24,1,13,78,123,4,21,66,168,35,3,18,33,96,51,49,72,22,41}。

例：初始?xì)w并段1為：2,5,6,12,16,23,27,39,44,45,55,78,123初始?xì)w并段2為：1,4,13,21,24,35,66,96,168初始?xì)w并段3為：3,18,22,33,41,49,51,72可見，利用置換-選擇排序所得到的初始?xì)w并段數(shù)明顯比直接用選擇排序少得多。如上面的例子，直接用選擇排序要生成六個(gè)初始?xì)w并段，但利用置換-選擇排序后，只得到了三個(gè)歸并段。

那么，利用置換-選擇排序到底能使初始?xì)w并段的長(zhǎng)度增加多少呢？

E.F.Moore用類比的辦法解決了這個(gè)問題：設(shè)天上正勻速地下著大雪，有一臺(tái)掃雪機(jī)也勻速地沿著一個(gè)環(huán)形跑道在掃雪，當(dāng)達(dá)到某一平衡點(diǎn)時(shí)，單位時(shí)間內(nèi)掃雪機(jī)掃去的雪和天上下的雪的量正好相等，跑道上的積雪量保持不變，則積雪形成了一個(gè)斜面：掃雪機(jī)前面的積雪厚度最大，掃雪機(jī)后面的積雪厚度為零。此時(shí)跑道上的積雪量就相當(dāng)于計(jì)算機(jī)的工作區(qū)大小W，而掃雪機(jī)工作一圈所掃去的積雪量就相當(dāng)于初始?xì)w并段的長(zhǎng)度——2W。生成初始?xì)w并段的時(shí)間（不考慮輸入輸出）為O(nlogW)?！?1.5緩沖區(qū)及并行操作設(shè)定相應(yīng)的輸入輸出緩沖區(qū)，讓輸入、輸出和內(nèi)部歸并三種操作同時(shí)進(jìn)行（并行操作），也能提高總的外部排序時(shí)間。但增加緩沖區(qū)數(shù)目，必將減小工作區(qū)大小W，又使得初始?xì)w并段長(zhǎng)度減小從而增加排序總時(shí)間。因此，外部排序總的時(shí)間與歸并排序路數(shù)k的選擇、緩沖區(qū)大小的設(shè)置以及各種外設(shè)參數(shù)的設(shè)置等有關(guān)，實(shí)際應(yīng)用時(shí)要綜合考慮各種因數(shù)?！?1.6最佳歸并樹

用置換-選擇排序得到的初始?xì)w并段長(zhǎng)度各不相同，那應(yīng)如何進(jìn)行k路平衡歸并呢？這實(shí)際上是建立k叉霍夫曼樹的問題：當(dāng)初始?xì)w并段總數(shù)不足（(m-1)MOD(k-1)≠0）時(shí)，需附加k-(m-1)MOD(k-1)-1個(gè)長(zhǎng)度為零的虛段，亦即第一次歸并時(shí)只對(duì)(m-1)MOD(k-1)+1個(gè)初始?xì)w并段歸并。建立k叉霍夫曼樹每次仍是選擇記錄數(shù)相對(duì)少的初始?xì)w并段先進(jìn)行歸并。最佳歸并樹不適合磁帶歸并排序。作業(yè)34.

已知某文件經(jīng)過置換-選擇排序之后，得到長(zhǎng)度分別為47，9，39，18，4，12，23和7的八個(gè)初始?xì)w并段。試為3-路平衡歸并設(shè)計(jì)一個(gè)讀寫外存次數(shù)最少的歸并方案，并求出總的讀寫外存次數(shù)?！?1.7磁帶歸并排序前面所介紹的各種技術(shù)除最佳歸并樹外均適合于磁帶歸并排序，但由于磁帶是順序存取設(shè)備，在實(shí)現(xiàn)外部排序時(shí)，有些特殊的問題需考慮。一、平衡歸并

實(shí)現(xiàn)k-路平衡歸并，需要2k臺(tái)磁帶機(jī)，其中k臺(tái)用于輸入，k臺(tái)用于輸出，待一趟歸并完后，輸入磁帶機(jī)改為輸出磁帶機(jī)，輸出磁帶機(jī)也改為輸入磁帶機(jī)，再進(jìn)行下一趟歸并；反復(fù)此過程，直至全部記錄歸并為一段有序序列。二、多步歸并

仔細(xì)分析一下磁帶k-路平衡歸并可以發(fā)現(xiàn)，其實(shí)只執(zhí)行一趟k-路歸并并不需要2k臺(tái)磁帶機(jī)，只需k+1臺(tái)磁帶機(jī)即可，多余的磁帶機(jī)目的是為了下一趟歸并。當(dāng)然，只用k+1臺(tái)磁帶機(jī)也能實(shí)現(xiàn)k-路平衡歸并，即在每趟歸并完后，再將各輸出歸并段（在同一磁帶機(jī)上）分配到k臺(tái)磁帶機(jī)上用于下一趟歸并。但這需要花費(fèi)很多時(shí)間，有沒有更好的辦法呢？

多步歸并排序（polyphasemerging

sorting）能解決這個(gè)矛盾。與平衡歸并不同，一趟多步歸并不是文件中的全部記錄都參與歸并。設(shè)有4臺(tái)磁帶機(jī)和17個(gè)初始?xì)w并段，采用3-路多步歸并排序，其歸并過程為：

例：

3-路多步歸并效率比3-路平衡歸并差，但比2-路平衡歸并強(qiáng)。那么，初始?xì)w并段又是如何分配在各磁帶機(jī)上的呢？利用k-階廣義費(fèi)波拉契序列，當(dāng)初始?xì)w并段總數(shù)為某一費(fèi)波拉契數(shù)（不足用虛段填充）時(shí)，各磁帶機(jī)上分布的初始?xì)w并段數(shù)由下式給出：t1(k)

=fj-1(k)+fj-2(k)+fj-3(k)+…+fj-k