一、外部排序
之前介紹的所有排序算法都是內(nèi)部排序的算法，也就是說需要將所有數(shù)據(jù)裝入內(nèi)存再進(jìn)行排序锰霜。但實際上會出現(xiàn)需要排序的數(shù)據(jù)太多無法全部裝入內(nèi)存的情況示姿，這種情況下排序就是外部排序甜橱，外部排序的基本思想就是歸并排序。
Tips：
歸并排序：兩個已排好序的數(shù)組栈戳，比較它們的第一個元素岂傲，選擇小(或大)的放入目標(biāo)數(shù)組，然后再比較各自的第一個元素子檀，一直重復(fù)至一個數(shù)組為空镊掖，然后將另一個數(shù)組剩余元素一一放入目標(biāo)數(shù)組。
1命锄、排序思路
外部排序的基礎(chǔ)思想也是歸并堰乔。
假設(shè)所有數(shù)據(jù)都在一個文件中，這個文件大小恰好是可用內(nèi)存的兩倍脐恩，先從文件中讀取一半的數(shù)據(jù)镐侯，然后用內(nèi)部排序算法將其排序，接著將這一半數(shù)據(jù)存入一個新的文件驶冒。然后再從文件中讀取剩下的一半的數(shù)據(jù)苟翻，同樣在內(nèi)存中將其排好序，存入一個新的文件中骗污。最后崇猫，打開這兩個文件，讀取各自的第一個數(shù)據(jù)需忿，比較后存入一個新文件诅炉，再讀取、比較屋厘、存入……最后數(shù)據(jù)全部存入這個文件中涕烧，完成排序。
在第一次讀取源數(shù)據(jù)的時候(即還沒開始第一次歸并)汗洒，每次讀取都是讀取主存能讀取的最大數(shù)據(jù)量议纯，假設(shè)為M，然后形成的單個“有序新文件”記為大小為M的“歸并段(順串)”
2溢谤、排序方法及時間
A瞻凤、2-路平衡歸并
舉例：一個文件含有10000條記錄，通過10次內(nèi)部排序得到10個初始?xì)w并段R1...R10世杀，其中每一段都含有1000個記錄阀参。然后兩兩歸并：
由10個初始?xì)w并段得到一個有序文件，共進(jìn)行了4趟歸并瞻坝，每一趟都從m個歸并段得到ceil(m/2)個歸并段蛛壳，這種歸并方法稱為2-路平衡歸并。
B、排序時間
外部排序所需總時間 = 內(nèi)部排序所需時間(m * tIS) + 外存信息讀寫時間(d * tIO) + 內(nèi)部歸并所需時間(s * utmg)
其中：
M：經(jīng)過內(nèi)部排序之后得到的初始?xì)w并段個數(shù)
tIS：得到一個初始?xì)w并段進(jìn)行內(nèi)部排序所需時間的平均值
d：總的讀/寫文件的次數(shù)
tIO：進(jìn)行一次外存讀/寫時間的平均值
s：歸并的趟數(shù)
utmg：對u個記錄進(jìn)行內(nèi)部歸并所需時間
上例中：假設(shè)每個物理塊(外存上信息的讀/寫以“物理塊”為單位進(jìn)行的)可以容納200條記錄炕吸，則每趟歸并(一個歸并段存儲1000條記錄)需進(jìn)行50次“讀”和50次“寫”，4趟歸并假設(shè)內(nèi)部排序時所需進(jìn)行的讀/寫使得在外排中共需進(jìn)行500次讀/寫勉痴。
則所需外排時間為：10tIS + 500tIO + 4 * 10000utmg
由此可見赫模，提高外排的效率應(yīng)主要減少外存信息讀寫的次數(shù)d。
C蒸矛、多路平衡歸并
若對上例進(jìn)行5路平衡歸并：
則僅需兩趟歸并瀑罗，總的讀/寫次數(shù)減少為2 * 100 + 100 = 300，比2路歸并減少了200次的讀/寫雏掠。
二斩祭、勝者樹和敗者樹
外部排序最耗時間的是磁盤讀寫，使用K路合并可以減少讀寫磁盤的次數(shù)乡话，但會增加算法復(fù)雜度摧玫，使用敗者樹可以加快合并排序。
勝者樹和敗者樹都是完全二叉樹绑青，是樹形選擇排序的一種變型诬像。每個葉子結(jié)點相當(dāng)于一個選手，每個中間結(jié)點相當(dāng)于一場比賽闸婴，每一層相當(dāng)于一輪比賽坏挠。
不同的是，勝者樹的中間結(jié)點記錄的是勝者的標(biāo)號邪乍；而敗者樹的中間結(jié)點記錄的敗者的標(biāo)號降狠。
勝者樹與敗者樹可以在log(n)的時間內(nèi)找到最值。任何一個葉子結(jié)點的值改變后庇楞，利用中間結(jié)點的信息榜配，還是能夠快速地找到最值。在k路歸并排序中經(jīng)常用到姐刁。
1芥牌、勝者樹
勝者樹的一個優(yōu)點是，如果一個選手的值改變了聂使，可以很容易地修改這棵勝者樹壁拉。只需要沿著從該結(jié)點到根結(jié)點的路徑修改這棵二叉樹，而不必改變其他比賽的結(jié)果柏靶。
上圖是勝者樹的示例：
b3 PK b4弃理，b3勝b4負(fù)，內(nèi)部結(jié)點ls[4]的值為3屎蜓；
b3 PK b0痘昌，b3勝b0負(fù)，內(nèi)部結(jié)點ls[2]的值為3；
b1 PK b2辆苔，b1勝b2負(fù)算灸，內(nèi)部結(jié)點ls[3]的值為1；
b3 PK b1驻啤，b3勝b1負(fù)菲驴，內(nèi)部結(jié)點ls[1]的值為3。
當(dāng)葉子結(jié)點b3的值變?yōu)?1時骑冗，重構(gòu)的勝者樹如下圖所示赊瞬。
b3 PK b4，b3勝b4負(fù)贼涩，內(nèi)部結(jié)點ls[4]的值為3巧涧；
b3 PK b0，b0勝b3負(fù)遥倦，內(nèi)部結(jié)點ls[2]的值為0谤绳；
b1 PK b2，b1勝b2負(fù)袒哥，內(nèi)部結(jié)點ls[3]的值為1闷供；
b0 PK b1，b1勝b0負(fù)统诺，內(nèi)部結(jié)點ls[1]的值為1歪脏。
2、敗者樹
敗者樹是勝者樹的一種變體粮呢。在敗者樹中婿失，用父結(jié)點記錄其左右子結(jié)點進(jìn)行比賽的敗者，而讓勝者參加下一輪的比賽啄寡。敗者樹的根結(jié)點記錄的是敗者豪硅，需要加一個結(jié)點來記錄整個比賽的勝利者。采用敗者樹可以簡化重構(gòu)的過程挺物。
上圖是一棵敗者樹懒浮，規(guī)定數(shù)大者敗。
b3 PK b4识藤，b3勝b4負(fù)砚著，內(nèi)部結(jié)點ls[4]的值為4；
b3 PK b0痴昧，b3勝b0負(fù)稽穆，內(nèi)部結(jié)點ls[2]的值為0；
b1 PK b2赶撰，b1勝b2負(fù)舌镶，內(nèi)部結(jié)點ls[3]的值為2柱彻；
b3 PK b1，b3勝b1負(fù)餐胀，內(nèi)部結(jié)點ls[1]的值為1哟楷；
在根結(jié)點ls[1]上又加了一個結(jié)點ls[0]=3，記錄的最后的勝者否灾。
敗者樹重構(gòu)過程如下：
將新進(jìn)入選擇樹的結(jié)點與其父結(jié)點進(jìn)行比賽：將敗者存放在父結(jié)點中吓蘑；而勝者再與上一級的父結(jié)點比較。
比賽沿著到根結(jié)點的路徑不斷進(jìn)行坟冲，直到ls[1]處。把敗者存放在結(jié)點ls[1]中溃蔫，勝者存放在ls[0]中健提。
上圖為當(dāng)b3變?yōu)?3時，敗者樹的重構(gòu)圖
敗者樹的重構(gòu)跟勝者樹是不一樣的伟叛，敗者樹的重構(gòu)只需要與其父結(jié)點比較私痹。對照敗者樹原圖來看，b3與結(jié)點ls[4]的原值比較统刮，ls[4]中存放的原值是結(jié)點4紊遵，即b3與b4比較，b3負(fù)b4勝侥蒙，則修改ls[4]的值為結(jié)點3暗膜。同理，以此類推鞭衩，沿著根結(jié)點不斷比賽学搜，直至結(jié)束。
由上可知论衍，敗者樹簡化了重構(gòu)瑞佩。敗者樹的重構(gòu)只是與該結(jié)點的父結(jié)點的記錄有關(guān)，而勝者樹的重構(gòu)還與該結(jié)點的兄弟結(jié)點有關(guān)坯台。
