轉(zhuǎn)自： https://mp.weixin.qq.com/s/KYbYTNl9PfXK--bG96YZJg
來(lái)源：帥地（本文來(lái)自作者的投稿锨苏，其簡(jiǎn)介見(jiàn)末尾）
背景
西天取經(jīng)的路上怜俐，一樣上演著編程的樂(lè)趣.....
排序的時(shí)候我們可以選擇快速排序或歸并排序等算法。為了方便，我們把排序好的2G有序數(shù)據(jù)稱(chēng)之為有序子串吧畔况。接著我們可以把兩個(gè)小的有序子串合并成一個(gè)大的有序子串鲸鹦。
注意：讀取的時(shí)候是每次讀取一個(gè)int數(shù)，通過(guò)比較之后在輸出跷跪。
按照這個(gè)方法來(lái)回合并馋嗜，總共經(jīng)過(guò)三次合并之后就可以得到8G的有序子串。
接下來(lái)把12個(gè)數(shù)據(jù)分成4份吵瞻，然后排序成有序子串
然后把子串進(jìn)行兩兩合并
輸出哪個(gè)元素葛菇，就在那個(gè)元素所在的有序子串再次讀入一個(gè)元素
繼續(xù)
重復(fù)直到合并成一個(gè)包含6個(gè)int的有序子串
再把兩個(gè)包含6個(gè)int的有序子串合并成一個(gè)包含12個(gè)int數(shù)據(jù)的最終有序子串
優(yōu)化策略
解釋下：例如對(duì)于數(shù)據(jù)2，我們把無(wú)序的12個(gè)數(shù)據(jù)分成有序的4個(gè)子串需要讀寫(xiě)各一次橡羞，把2份3個(gè)有序子串合并成6個(gè)有序子串讀寫(xiě)各一次眯停；把2份6個(gè)有序子串合并從12個(gè)有序子串讀寫(xiě)各一次，一共需要讀寫(xiě)各3次卿泽。
多路歸并
為了方便講解莺债，我們假設(shè)內(nèi)存一共可以裝4個(gè)int型數(shù)據(jù)。
置換選擇
例如我們可以從12個(gè)數(shù)據(jù)讀取3個(gè)存到內(nèi)存中签夭，然后從內(nèi)存中選出最小的那個(gè)數(shù)放進(jìn)子串p1里齐邦；
之后再?gòu)脑趶氖Ｓ嗟?個(gè)數(shù)據(jù)讀取一個(gè)放到內(nèi)存中，然后再?gòu)膬?nèi)存中選出一個(gè)數(shù)放進(jìn)子串p1里第租，這個(gè)數(shù)必須滿(mǎn)足比p1中的其他數(shù)大措拇，且在內(nèi)存中盡量小。
這樣一直重復(fù)慎宾，直到內(nèi)存中的數(shù)都比p1中的數(shù)小丐吓，這時(shí)p1子串存放結(jié)束浅悉，繼續(xù)來(lái)p2子串的存放。例如(這時(shí)假設(shè)內(nèi)存只能存放3個(gè)int型數(shù)據(jù))：
12個(gè)無(wú)序的int數(shù)據(jù)
讀入3個(gè)到內(nèi)存中汰蜘，且選出一個(gè)最小的到子串p1
從內(nèi)存中再次讀取一個(gè)元素86
從內(nèi)存中再次讀取一個(gè)元素3
從內(nèi)存中再次讀取一個(gè)元素24
從內(nèi)存中再次讀取一個(gè)元素8
這個(gè)時(shí)候仇冯，已經(jīng)沒(méi)有符合要求的數(shù)了，且內(nèi)存已滿(mǎn)族操，進(jìn)而用p2子串來(lái)存放苛坚，以此類(lèi)推。
通過(guò)這種方法色难，p1子串存放了4個(gè)數(shù)據(jù)泼舱，而原來(lái)的那種方法p1子串只能存放3個(gè)數(shù)據(jù)。
從12個(gè)數(shù)據(jù)中讀取3個(gè)數(shù)據(jù)枷莉，構(gòu)建成一個(gè)最小堆娇昙，然后從堆頂選擇一個(gè)數(shù)寫(xiě)入到p1中。
之后再?gòu)氖Ｓ嗟?個(gè)數(shù)中讀取一個(gè)數(shù)笤妙，如果這個(gè)數(shù)比剛才那個(gè)寫(xiě)入到p1中的數(shù)大冒掌，則把這個(gè)數(shù)插入到最小堆中，重新調(diào)整最小堆結(jié)構(gòu)蹲盘，然后在堆頂選一個(gè)數(shù)寫(xiě)入到p1中股毫。
否則，把這個(gè)數(shù)暫放在一邊召衔，暫時(shí)不處理铃诬。之后一樣需要調(diào)整堆結(jié)構(gòu)，從堆頂選擇一個(gè)數(shù)寫(xiě)入到p1中苍凛。
這里說(shuō)明一下趣席，那個(gè)被放在一邊的數(shù)是不能再放入p1中的了，因?yàn)樗欢ū萷1中的數(shù)都要小醇蝴，所以它會(huì)放在下一個(gè)子串中
看這些文字會(huì)讓人頭大宣肚，我畫(huà)圖解釋下吧。
從12數(shù)據(jù)讀取3個(gè)數(shù)據(jù)
構(gòu)建最小堆悠栓，且選出目標(biāo)數(shù)
讀入下一個(gè)數(shù)86
讀入下一個(gè)數(shù)3钉寝，比70小，暫放一邊闸迷，不加入堆結(jié)構(gòu)中
讀入下一個(gè)數(shù)據(jù)24嵌纲，比81小，不加入堆結(jié)構(gòu)
讀入下一個(gè)數(shù)據(jù)8腥沽，比86小逮走，不加入堆結(jié)構(gòu)。此時(shí)p1已經(jīng)完成了今阳，把那些剛才暫放一邊的數(shù)重新構(gòu)成一個(gè)堆师溅，繼續(xù)p2的存放茅信。
以此類(lèi)推...
最后生成的p2如下：
這種方法適合要排序的數(shù)據(jù)太多，以至于內(nèi)存一次性裝載不下墓臭。只能通過(guò)把數(shù)據(jù)分幾次的方式來(lái)排序蘸鲸，我們也把這種方法稱(chēng)之為外部排序
