7-6外部排序v第七章排序技術(shù)學(xué)什么？外部排序的基本思想置換-選擇排序敗者樹(shù)為什么外部排序需要新算法？外部排序需要著重考慮什么？基本思想外部排序的基本思想：采用多路歸并排序，分為以下兩個(gè)階段：外部排序（externalsorting）：待排序的記錄以文件的形式存儲(chǔ)在外存上，在排序過(guò)程中需要在內(nèi)存和外存之間進(jìn)行多次數(shù)據(jù)交換預(yù)處理階段：根據(jù)可用內(nèi)存的大小，將原文件分解成多個(gè)能夠一次性裝入內(nèi)存的子文件，分別對(duì)每一個(gè)子文件在內(nèi)存中完成排序，得到若干個(gè)有序的子文件（稱(chēng)為歸并段）；歸并排序階段：對(duì)歸并段進(jìn)行若干趟多路歸并排序，直至將整個(gè)文件的記錄排好序。為什么外部排序在歸并排序階段采用多路歸并呢？R1R2R3R4R5R6R7R8R9R10R11R12歸并段及歸并結(jié)果不能同時(shí)存放在內(nèi)存中，需要多次對(duì)外存進(jìn)行讀/寫(xiě)操作?；舅枷隦13R14R13R14R15R1R2R3R4R5R6R7R8R15多路歸并可以減少歸并排序的趟數(shù)對(duì)外存讀/寫(xiě)操作的次數(shù)和歸并排序的趟數(shù)成正比置換-選擇排序假設(shè)待排序文件有

n個(gè)記錄，內(nèi)存緩沖區(qū)的容量是

k，每次將

k個(gè)記錄讀入內(nèi)存進(jìn)行排序，得到歸并段的個(gè)數(shù)是多少？

如何增大歸并段的記錄個(gè)數(shù)呢？如何減少歸并排序執(zhí)行的趟數(shù)呢？采用多路歸并

k-路歸并排序

在k

個(gè)記錄中取出最小值

敗者樹(shù)減少歸并段的個(gè)數(shù)

增大歸并段的記錄個(gè)數(shù)增大k歸并段的個(gè)數(shù)是n/k算法：置換-選擇排序輸入：待排序文件FI輸出：歸并段文件FO1.從文件FI中讀取

w個(gè)記錄到內(nèi)存緩沖區(qū)buf；2.從buf中選取值最小的記錄，記為

rmin；3.將

rmin輸出到FO；4.若FI不空，則從FI中讀取1個(gè)記錄到buf中，轉(zhuǎn)步驟5；否則，重復(fù)執(zhí)行步驟2和步驟3，直至緩沖區(qū)buf為空，算法結(jié)束；5.從buf中所有比記錄

rmin值大的記錄中，選取值最小的記錄，重新記為

rmin，轉(zhuǎn)步驟3；6.如果buf中沒(méi)有比記錄

rmin值大的記錄，則得到1個(gè)初始?xì)w并段，轉(zhuǎn)步驟2構(gòu)造下一個(gè)歸并段；假設(shè)內(nèi)存緩沖區(qū)buf可容納

w個(gè)記錄，假設(shè)每個(gè)物理塊只能容納1個(gè)記錄置換-選擇排序例1假設(shè)內(nèi)存緩沖區(qū)buf可容納4個(gè)記錄，文件FI包含的記錄為{10,20,12,18,6,25,5,22,15,30,28,10}，寫(xiě)出置換-選擇排序的過(guò)程。歸并段2615285歸并段1內(nèi)存緩沖區(qū)102012181528對(duì)于長(zhǎng)度不等的初始?xì)w并段，不同的多路歸并方案對(duì)排序性能有什么影響？620121810620251812186202552062225561525522615305256152853061528105152810615281028置換-選擇排序最佳歸并樹(shù)例2置換-選擇排序生成了9個(gè)初始?xì)w并段，長(zhǎng)度分別為{9,30,12,18,3,17,2,6,24}，假設(shè)采用3-路歸并排序。9301251183173826243212123611912321718245932121WPL=242WPL=223最佳歸并樹(shù)：帶權(quán)路徑長(zhǎng)度最小的歸并樹(shù)。對(duì)于長(zhǎng)度不等的初始?xì)w并段，不同的多路歸并方案對(duì)排序性能有什么影響？方案1：方案2：最佳歸并樹(shù)需添加(k-1)-(n-1)mod(k-1)個(gè)虛段具有n個(gè)初始?xì)w并段，合并為k-路最佳歸并樹(shù)，需要填加多少個(gè)虛段？2311912321718245932121什么是虛段？長(zhǎng)度為0的歸并段敗者樹(shù)如何快速在多個(gè)記錄中選取值最小的記錄？順序查找

k–1次比較敗者樹(shù)

O(log2k)敗者樹(shù)（treeofloser）：分支結(jié)點(diǎn)表示左、右孩子結(jié)點(diǎn)中的敗者，讓勝者去參加更高一層的比較。勝者樹(shù)—