內(nèi)排序的歸并排序是采用二路歸并近她。
將已有序的子序列合并鼻忠，得到完全有序的序列驰吓；即先使每個(gè)子序列有序混蔼，再使子序列段間有序
外排序我們可以將這個(gè)“二”擴(kuò)大到M履腋。
將一個(gè)大文件分成M個(gè)小文件，每個(gè)小文件是有序的惭嚣，然后對(duì)應(yīng)在內(nèi)存中我們開M個(gè)優(yōu)先隊(duì)列遵湖，每個(gè)隊(duì)列從對(duì)應(yīng)編號(hào)的文件中讀取TopN條記錄，然后我們從M路隊(duì)列中各取一個(gè)數(shù)字進(jìn)入中轉(zhuǎn)站隊(duì)列晚吞，并將該數(shù)字打上隊(duì)列編號(hào)標(biāo)記奄侠，當(dāng)從中轉(zhuǎn)站出來的最小數(shù)字就是我們最后要排序的數(shù)字之一，因?yàn)樵摂?shù)字打上了隊(duì)列編號(hào)载矿，所以方便我們通知對(duì)應(yīng)的編號(hào)隊(duì)列繼續(xù)出數(shù)字進(jìn)入中轉(zhuǎn)站隊(duì)列，可以看出中轉(zhuǎn)站一直保存了M個(gè)記錄烹卒，當(dāng)中轉(zhuǎn)站中的所有數(shù)字都出隊(duì)完畢闷盔，則外排序結(jié)束。這考驗(yàn)的是我們的架構(gòu)能力旅急。
問題描述：
輸入：給定一個(gè)文件逢勾，里面最多含有n個(gè)不重復(fù)的正整數(shù)（也就是說可能含有少于n個(gè)不重復(fù)正整數(shù)），且其中每個(gè)數(shù)都小于等于n藐吮，n=10^7溺拱。
輸出：得到按從小到大升序排列的包含所有輸入的整數(shù)的列表。
條件：最多有大約1MB的內(nèi)存空間可用谣辞，但磁盤空間足夠迫摔。且要求運(yùn)行時(shí)間在5分鐘以下，10秒為最佳結(jié)果泥从。
采取方法：1句占、歸并排序，內(nèi)存不夠躯嫉。2纱烘、位圖法杨拐。3、多路歸并
1擂啥、歸并排序哄陶，內(nèi)部排序。
2哺壶、位圖法
例如：用一個(gè)20位長的字符串來表示一個(gè)所有元素都小于20的簡(jiǎn)單的非負(fù)整數(shù)集合屋吨，邊框用如下字符串來表示集合{1,2,3,5,8,13}：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0，上述集合中各數(shù)對(duì)應(yīng)的位置則置1变骡，沒有對(duì)應(yīng)的數(shù)的位置則置0离赫。
針對(duì)我們的10^7個(gè)數(shù)據(jù)量的磁盤文件排序問題，我們可以這么考慮塌碌，由于每個(gè)7位十進(jìn)制整數(shù)表示一個(gè)小于1000萬的整數(shù)渊胸。我們可以使用一個(gè)具有1000萬個(gè)位的字符串來表示這個(gè)文件，其中台妆，當(dāng)且僅當(dāng)整數(shù)i在文件中存在時(shí)翎猛，第i位為1。采取這個(gè)位圖的方案是因?yàn)槲覀兠鎸?duì)的這個(gè)問題的特殊性：1接剩、輸入數(shù)據(jù)限制在相對(duì)較小的范圍內(nèi)切厘，2、數(shù)據(jù)沒有重復(fù)懊缺，3疫稿、其中的每條記錄都是單一的整數(shù)，沒有任何其它與之關(guān)聯(lián)的數(shù)據(jù)鹃两。
三步進(jìn)行解決：
第一步遗座，將所有的位都置為0，從而將集合初始化為空俊扳。
第二步途蒋，通過讀入文件中的每個(gè)整數(shù)來建立集合，將每個(gè)對(duì)應(yīng)的位都置為1馋记。
第三步号坡，檢驗(yàn)每一位，如果該位為1梯醒，就輸出對(duì)應(yīng)的整數(shù)宽堆。
注意：
用此位圖方法，嚴(yán)格說來還是不太行茸习，空間消耗10^7/8還是大于1M（1M=1024*1024空間日麸，小于10^7/8）。
既然如果用位圖方案的話，我們需要約1.25MB（若每條記錄是8位的正整數(shù)的話代箭，則10000000/(1024*1024*8) ~= 1.2M）的空間墩划，而現(xiàn)在只有1MB的可用存儲(chǔ)空間，那么究竟該作何處理呢?
3嗡综、多路歸并
假設(shè)文件中整數(shù)個(gè)數(shù)為N(N是億級(jí)的)乙帮，整數(shù)之間用空格分開。首先分多次從該文件中讀取M（十萬級(jí)）個(gè)整數(shù)极景，每次將M個(gè)整數(shù)在內(nèi)存中使用快速排序之后存入臨時(shí)文件察净，然后使用多路歸并將各個(gè)臨時(shí)文件中的數(shù)據(jù)再次整體排好序后存入輸出文件。
排序過程兩部分構(gòu)成：
1）內(nèi)存排序
由于要求的可用內(nèi)存為1MB盼樟，那么每次可以在內(nèi)存中對(duì)250K的數(shù)據(jù)進(jìn)行排序氢卡，然后將有序的數(shù)寫入硬盤。
那么10M的數(shù)據(jù)需要循環(huán)40次晨缴，最終產(chǎn)生40個(gè)有序的文件译秦。
2）歸并排序
將每個(gè)文件最開始的數(shù)讀入(由于有序，所以為該文件最小數(shù))击碗，存放在一個(gè)大小為40的first_data數(shù)組中筑悴；
選擇first_data數(shù)組中最小的數(shù)min_data，及其對(duì)應(yīng)的文件索引index稍途；
將first_data數(shù)組中最小的數(shù)寫入文件result阁吝，然后更新數(shù)組first_data(根據(jù)index讀取該文件下一個(gè)數(shù)代替min_data)；
判斷是否所有數(shù)據(jù)都讀取完畢械拍，否則返回2突勇。
所以，本程序按順序分兩步坷虑，第一步甲馋、Memory Sort，第二步猖吴、Merge Sort。程序的流程圖挥转，如下圖所示（感謝F的繪制）海蔽。
小結(jié)：
bit-map
適用范圍：可進(jìn)行數(shù)據(jù)的快速查找，判重绑谣，刪除党窜，一般來說數(shù)據(jù)范圍是int的10倍以下
基本原理及要點(diǎn)：使用bit數(shù)組來表示某些元素是否存在，比如8位電話號(hào)碼
擴(kuò)展：bloom filter可以看做是對(duì)bit-map的擴(kuò)展
問題實(shí)例：
1)已知某個(gè)文件內(nèi)包含一些電話號(hào)碼借宵，每個(gè)號(hào)碼為8位數(shù)字幌衣，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。
8位最多99 999 999，大概需要99m個(gè)bit豁护，大概10幾m字節(jié)的內(nèi)存即可哼凯。
2)2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)楚里。
將bit-map擴(kuò)展一下断部，用2bit表示一個(gè)數(shù)即可，0表示未出現(xiàn)班缎，1表示出現(xiàn)一次蝴光，2表示出現(xiàn)2次及以上〈镏罚或者我們不用2bit來進(jìn)行表示蔑祟，我們用兩個(gè)bit-m
[外排序適用范圍]
大數(shù)據(jù)的排序，去重基本原理及要點(diǎn)：外排序的歸并方法沉唠，置換選擇敗者樹原理疆虚，最優(yōu)歸并樹擴(kuò)展。
問題實(shí)例：
1).有一個(gè)1G大小的一個(gè)文件右冻，里面每一行是一個(gè)詞装蓬，詞的大小不超過16個(gè)字節(jié)，內(nèi)存限制大小是1M纱扭。返回頻數(shù)最高的100個(gè)詞牍帚。這個(gè)數(shù)據(jù)具有很明顯的特點(diǎn)，詞的大小為16個(gè)字節(jié)乳蛾，但是內(nèi)存只有1m做hash有些不夠暗赶，所以可以用來排序。內(nèi)存可以當(dāng)輸入緩沖區(qū)使用肃叶。
具體實(shí)例詳解：
鏈接 ：http://www.reibang.com/p/1683cf5cc0c9
勝者樹蹂随，敗者樹
勝者樹和敗者樹都是完全二叉樹，是樹形選擇排序的一種變型因惭。每個(gè)葉子結(jié)點(diǎn)相當(dāng)于一個(gè)選手岳锁，每個(gè)中間結(jié)點(diǎn)相當(dāng)于一場(chǎng)比賽，每一層相當(dāng)于一輪比賽蹦魔。
同的是激率，勝者樹的中間結(jié)點(diǎn)記錄的是勝者的標(biāo)號(hào)；而敗者樹的中間結(jié)點(diǎn)記錄的敗者的標(biāo)號(hào)勿决。
勝者樹與敗者樹可以在log(n)的時(shí)間內(nèi)找到最值乒躺。任何一個(gè)葉子結(jié)點(diǎn)的值改變后，利用中間結(jié)點(diǎn)的信息低缩，還是能夠快速地找到最值嘉冒。在k路歸并排序中經(jīng)常用到。
區(qū)別：
在用勝者樹的時(shí)候，每個(gè)新元素上升時(shí)讳推，首先需要獲得父節(jié)點(diǎn)顶籽，然后再獲得兄弟節(jié)點(diǎn)，然后再比較娜遵。
在使用敗者樹的時(shí)候蜕衡，每個(gè)新元素上升時(shí)，只需要獲得父節(jié)點(diǎn)并比較即可设拟。
所以總的來說慨仿，減少了訪存的時(shí)間。
勝者樹和敗者樹在每輸出和補(bǔ)充一個(gè)值之后都要自底向上調(diào)整纳胧，每上升一層都需要一次比較镰吆，敗者樹是和父節(jié)點(diǎn)的一次比較，勝者樹是和兄弟的一次比較跑慕，在比較的內(nèi)存訪問次數(shù)上二者沒有太大的差別(或者勝者樹可能好一點(diǎn))万皿。不同的是勝者樹每次必然需要更新勝者(因?yàn)檫@條路徑就是以原來的最終勝者為外部節(jié)點(diǎn)的路徑，而原來的最終勝者已經(jīng)被輸出了)核行，但敗者樹每次不一定需要更新牢硅，這就代表它在每次上升時(shí)可能會(huì)少一次向內(nèi)存的寫入，因此更優(yōu)
由于新加入的節(jié)點(diǎn)一定是替換了上一輪的勝者芝雪，那么對(duì)于勝者堆减余，從新節(jié)點(diǎn)到根之間路徑節(jié)點(diǎn)存的都是上一輪的勝者，這些數(shù)據(jù)事實(shí)上對(duì)于本輪比較來說是無用的惩系，但每次還要與兄弟節(jié)點(diǎn)比較去更新它位岔。
而敗者堆中，對(duì)于新更新的節(jié)點(diǎn)堡牡，它的父節(jié)點(diǎn)都是兄弟子堆的勝者抒抬，是最有價(jià)值、值得比較的數(shù)據(jù)晤柄，每次更新也都可以直接用于下輪比較擦剑。
http://blog.csdn.net/v_JULY_v/article/details/6451990 ?（贊）
http://blog.csdn.net/v_JULY_v/article/details/6279498 ?（超贊）
http://www.cnblogs.com/charlesblc/p/6138908.html
http://blog.csdn.net/msdnwolaile/article/details/52084983
http://blog.csdn.net/u013322907/article/details/38125641
http://blog.csdn.net/msdnwolaile/article/details/52084983
http://blog.csdn.net/v_JULY_v
http://blog.csdn.net/whz_zb/article/details/7425152
https://www.zhihu.com/question/35144290
