如何對1TB的數組進行排序？

01-04

這題我知道是很經典的面試題，但是我比較想知道有米有綜合完整版的回答？

知道 Merge Sort 嗎？

知道的話，如果把數組放硬碟上，合併的部分在內存中處理的話……

參考外部排序

我說一個分散式的方法。

先把1TB數據按照range hash到n個結點上，保證後一個節點所有的記錄值都大於前一個節點，再分別排序，最終生成n個輸出文件，這已經是排好序的了。

為了保證每個節點處理的數據量差不多可以先對數據進行採樣，估計一下分布並因此來設置hash函數。

這種方法也適合更大的數據量，更大數據量的時候輸入數據就會存在多台機器上，此時用就需要做map reduce的操作了。對的沒錯，這就是Spark的sortByKey()的做法。

先根據你的內存將大文件分段，比如：

你的可用內存有1GB，那麼就要將大文件分成

1TB / 1GB = 1000段

然後將每段依次讀入內存，在內存中使用內部排序演算法(例如快速排序，堆排序等)將其排好序，然後將其輸出成各個分段文件，例如：

file1，file2，...，file1000

然後對這一千個分段文件的文件頭(或文件指針)，建立一顆敗者樹，用來選取當前最小的元素(或最大的元素，依你的排序要求而定)

並將這最小的元素輸出到最終的輸出文件里。

重複這一過程，直到1000個分段文件全部被輸出。刪去這1000個分段文件，僅保留最終的輸出文件，即得到排好序的文件。

TAOCP Volume 3. 5.4 External Sort. 第一節講了通用做法：Replacement Selection之後Multiway Merge。

這章假設數據是存在磁帶上，所以後面幾節講了怎麼樣減少磁帶的讀。比如polyphase merge，如果你的磁帶初始run的分布是Fibonacci分布的話，讀磁帶的遍數就最少。

實際上，如果是4位元組int類型的話，由於數量有限（2^32個），遍歷其中每個數一次只需要16GB的內存。這個時候，記下每個數出現的次數再整理一遍或許是最好的方法，而且時間複雜度還是o(n)

外排+敗者樹

如果數據結構特殊可以考慮其他方法，比如如果不重複的數據可以考慮點陣圖

1. 分析數據的特點，完全亂序還是部分有序？

2. 選擇演算法。選擇一種適合數據的演算法，兼顧演算法是否可並行化，時間複雜度，空間複雜度。

3. 少量數據來測試演算法，並對演算法進行改進。

4. 一切OK後來做大規模測試，並做好log。

寫入資料庫，order by

外部排序，比如歸併排序？

如果數據空間不（太）大而可用內存足夠多那麼可以嘗試統計排序

我提供個優化操作。

1T無重複的話，int就存不下了。這時可以用一些技巧比如先排高位，再排低位，最後多路歸併，提高cache命中率。

有重複且都為int型的話，提前過濾遍，能極大的減少計算量。

另外如果可以用sse指令集，那麼用這個運算效率也可以提高好幾倍。

置換選擇+敗者樹

hadoop 的mapreduce

歸併雖然在內部排序表現不佳，但是外部排序確實是對的。請查找外部排序，歸併排序等關鍵字。

有一種東西叫虛擬內存，還有另外一種東西叫IO，懶就搞1t虛擬內存，不知道支不支持，勤快就自己寫一個快排或者歸併，對文件進行操作，當然這個歸併不要用遞歸，用循環

把1tb的數據分成多個文件，然後進行歸併排序