外部排序

為什么要學(xué)習(xí)外部排序？
答：
在處理數(shù)據(jù)的過(guò)程中，我們需要把磁盤(pán)(外存）中存儲(chǔ)的數(shù)據(jù)拿到內(nèi)存中處理，因?yàn)閮?nèi)存處理更快，但是由于內(nèi)存空間較小，外存空間很大，外存中的數(shù)據(jù)元素太多，無(wú)法一次全部讀入內(nèi)存進(jìn)行排序。所以，通過(guò)外部排序就是實(shí)現(xiàn)對(duì)于外存存儲(chǔ)元素排序的方法。

1.最基本的外部排序原理

假設(shè)在外存中，我們有48個(gè)記錄，按照每三個(gè)記錄為一塊，建立好基本16個(gè)分塊。
注意：在建立基本的分塊之前，外存的每個(gè)小分塊要先進(jìn)行內(nèi)部排序，保證這16個(gè)分塊內(nèi)部是有序的。
內(nèi)存中，有2個(gè)輸入緩沖區(qū)和1個(gè)輸出緩沖區(qū)，采用歸并排序的思想，第一次，先從16個(gè)分塊中拿出兩塊，分別放入緩沖區(qū)1和緩沖區(qū)2.然后每次從這兩個(gè)緩沖區(qū)6的開(kāi)頭，選最小的，放入輸出緩沖區(qū)，然后湊齊3個(gè)記錄，就回填外存。以此類(lèi)推，直到把這1個(gè)分塊，變?yōu)?個(gè)分塊。

第二次開(kāi)始，本質(zhì)還是這個(gè)過(guò)程，但是值得注意的是，我們必須保證輸入緩沖區(qū)不空，即如果一旦一個(gè)緩沖區(qū)的元素被拿空了，要立刻用該分塊的其它元素補(bǔ)上。

外部排序時(shí)間開(kāi)銷(xiāo)=讀寫(xiě)外存的時(shí)間+內(nèi)部排序所需時(shí)間+內(nèi)部歸并所需時(shí)間

不難得知，采用多路歸并可以減少歸并趟數(shù)。

記結(jié)論：
生成初始片段r個(gè)，進(jìn)行k路歸并
則趟數(shù)S=?log_k^r?

2.外部排序的優(yōu)化

2.1 敗者樹(shù)優(yōu)化方法

敗者樹(shù)用來(lái)減少關(guān)鍵字的比較次數(shù)。

將各個(gè)歸并段段開(kāi)頭加入到敗者樹(shù)的葉子結(jié)點(diǎn)，然后開(kāi)始構(gòu)造敗者樹(shù)，注意，中間結(jié)點(diǎn)記錄的是，當(dāng)前勝者是來(lái)自哪個(gè)歸并端，在得到冠軍來(lái)自3號(hào)歸并端后，將3號(hào)歸并段的葉子結(jié)點(diǎn)移除，將3號(hào)歸并段新的結(jié)點(diǎn)補(bǔ)上，此時(shí)，不需要比較太多次，通過(guò)敗者樹(shù)向上比較，就可以得出新的冠軍，以此類(lèi)推。

效率分析：
對(duì)于k路歸并，第一次構(gòu)造敗者樹(shù)需要對(duì)比關(guān)鍵字k-1次，
有了敗者樹(shù)，選出最小元素，只需要對(duì)比?log₂^k?

2.2 置換-選擇排序優(yōu)化方法

讓歸并段更少，即讓歸并段更長(zhǎng)。

初始待排序文件，不斷的將當(dāng)前內(nèi)存工作區(qū)中，大于minmax的最小值，加入歸并段中，每加入一個(gè)，再?gòu)某跏即判蛭募醒a(bǔ)充一個(gè)，直到內(nèi)存工作區(qū)中的所有元素都小于minmax，然后開(kāi)始輸出歸并段2，更改minmax，重復(fù)上述過(guò)程。

2.3 最佳歸并樹(shù)

對(duì)于歸并過(guò)程進(jìn)一步優(yōu)化。

只講干貨：
每個(gè)初始?xì)w并端對(duì)應(yīng)一個(gè)葉子結(jié)點(diǎn)，把歸并段段塊數(shù)作為葉子的權(quán)值。最好的歸并的過(guò)程其實(shí)就是構(gòu)造哈夫曼樹(shù)的過(guò)程。
歸并樹(shù)的WPL=歸并過(guò)程中的磁盤(pán)I/O次數(shù)

值得注意的是，k叉歸并的最佳歸并樹(shù)一定是嚴(yán)格k叉樹(shù)，所以很可能葉子結(jié)點(diǎn)的個(gè)數(shù)不滿(mǎn)足構(gòu)造嚴(yán)格k叉歸并樹(shù)，這時(shí)候需要補(bǔ)充虛段(權(quán)值為0的葉子結(jié)點(diǎn)，然后將這些權(quán)值為0的結(jié)點(diǎn)作為最初始的構(gòu)造結(jié)點(diǎn).

補(bǔ)充虛段的數(shù)量有公式：
（初始?xì)w并段數(shù)量-1)%（k-1）=u
若u=0,則說(shuō)明不需要添加虛段，否則添加(k-1)-u個(gè)虛段。

下圖是一個(gè)3路歸并的最佳歸并樹(shù)。