一道面試題：4G內存， 100G文件，文件中存放字符串，排序這100G文件字符串數據
內部排序：
內存中可以存放所有待排序的數據，可以使用高效的內部排序來完成例如快速排序，歸并排序，堆排序等。
外部排序：
待排序數據過大，內存不能一次全部加載來完成排序。一般采用分段加載內部排序，然后多路合并，產生最后排序結果。
1. 基本實現方式：
將100G文件分成100份排號為1,2...100，每份1G加載進內存，然后對每份文件采用內部排序來排序，字符串應該有高效的內部排序方式，將排序結果寫入到100份文件中，每份文件都是有序的；
將內存分成3份 1G 1G 2G ，從文件1加載到內存中，從文件2數據到內存中，將這兩個文件數據進行歸并排序，最終結果寫到一個2G文件中，這樣依次進行歸并排序，可以產生50份2G文件；進行進行歸并直到整個文件有序。
存在的問題： 文件大小的劃分，歸并排序可以采用多路歸并排序。
大神的一個例子，假設有一個含10000 個記錄的文件，首先通過10 次內部排序得到10 個初始歸并段R1～R10 ，其中每一段都含1000 個記錄。然后對它們作兩兩歸并，直至得到一個有序文件為止：
2.多路歸并方式：
普通兩路歸并方式，每次歸并兩個文件，即從兩個文件中選取較小者放入到目標文件中，可以采用K路歸并方式，即每一次歸并K個文件,即從K個文件中選取較小者放入到目標文件中。增大k可以減少外存信息讀寫時間，但k個歸并段中選取最小的記錄需要比較k-1次，為得到u個記錄的一個有序段共需要(u-1)(k-1)次，若歸并趟數為s次，那么對n個記錄的文件進行外排時，內部歸并過程中進行的總的比較次數為s(n-1)(k-1)。若共有m個歸并段，則s=logkm,所以總的比較次數為： (logkm)(k-1)(n-1)=(log2m/log2k)(k-1)(n-1)，而(k-1)/log2k隨k增而增因此內部歸并時間隨k增長而增長了，抵消了外存讀寫減少的時間，這樣做不行，由此引出了“敗者樹”tree of loser的使用。在內部歸并過程中利用敗者樹將k個歸并段中選取最小記錄比較的次數降為(log2k)次，使總比較次數為(log2m)(n-1)與k無關。
敗者樹是完全二叉樹，可以采用一維數組。其元素個數為k個葉子結點、k-1個比較結點、1個冠軍結點共2k個。ls[0]為冠軍結點，ls[1]--ls[k-1]為比較結點，ls[k]--ls[2k-1]為葉子結點（同時用另外一個指針索引b[0]--b[k-1]指向）。另外bk為一個附加的輔助空間，不屬于敗者樹，初始化時存著MINKEY的值。
多路歸并排序算法的過程大致為：
1）：首先將k個歸并段中的首元素關鍵字依次存入b[0]--b[k-1]的葉子結點空間里，然后創建敗者樹，創建完畢之后最小的關鍵字下標（即所在歸并段的序號）便被存入ls[0]中。然后不斷循環：
2）把ls[0]所存最小關鍵字來自于哪個歸并段的序號得到為q，將該歸并段的首元素輸出到有序歸并段里，然后把下一個元素關鍵字放入上一個元素本來所在的葉子結點b[q]中，調用Adjust順著b[q]這個葉子結點往上調整敗者樹直到新的最小的關鍵字被選出來，其下標同樣存在ls[0]中。循環這個操作過程直至所有元素被寫到有序歸并段里。
以4路歸并排序為例，葉子結點存放每個歸并段的最小值，然后依次進行比較，失敗者成為根節點，成功者進行下一輪比較，5,7 7失敗成為根節點，5成功 29,9 29失敗為根節點 9成功 5，9下一輪比較 5成功寫入輸出緩沖區，9失敗成為根節點
由于5最小，已經輸出，因此把輸出元素所在的歸并路加載下一個元素，再依次進行比較，有點類似于堆排序，每次將最小的元素輸出。
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯系我們，我們將根據著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
