經典算法題每日演練——第十八題 外排序

     說到排序，大家第一反應基本上是内排序，是的，算法嘛，玩的就是記憶體，然而記憶體是有限制的，總有裝不下的那一天，此時就可以來玩玩

外排序，當然在我看來，外排序考驗的是一個程式員的架構能力，而不僅僅局限于排序這個層次。

一：n路歸并排序

1.概序

    我們知道算法中有一種叫做分治思想，一個大問題我們可以采取分而治之，各個突破，當子問題解決了，大問題也就ko了，還有一點我們知道

内排序的歸并排序是采用二路歸并的，因為分治後有logn層，每層兩路歸并需要n的時候，最後複雜度為nlogn，那麼外排序我們可以将這個“二”

擴大到m，也就是将一個大檔案分成m個小檔案，每個小檔案是有序的，然後對應在記憶體中我們開m個優先隊列，每個隊列從對應編号的檔案中讀取

topn條記錄，然後我們從m路隊列中各取一個數字進入中轉站隊列，并将該數字打上隊列編号标記，當從中轉站出來的最小數字就是我們最後要排

序的數字之一，因為該數字打上了隊列編号，是以友善我們通知對應的編号隊列繼續出數字進入中轉站隊列，可以看出中轉站一直儲存了m個記錄，

當中轉站中的所有數字都出隊完畢，則外排序結束。如果大家有點蒙的話，我再配合一張圖，相信大家就會一目了然，這考驗的是我們的架構能力。

圖中這裡有個batch容器，這個容器我是基于性能考慮的，當batch=n時，我們定時重新整理到檔案中，保證記憶體有足夠的空間。

2.建構

<1> 生成資料

   這個基本沒什麼好說的，采用随機數生成n條記錄。

　　

<2> 切分資料

     根據實際情況我們來決定到底要分成多少個小檔案，并且小檔案的資料必須是有序的，小檔案的個數也對應這記憶體中有多少個優先隊列。

<3> 加入隊列

    我們知道記憶體隊列存放的隻是小檔案的topn條記錄，當記憶體隊列為空時，我們需要再次從小檔案中讀取下一批的topn條資料，然後放入中轉站

繼續進行比較。

<4> 測試

 最後我們來測試一下:

 資料量：short.maxvalue。

 記憶體存放量：1200。

在這種場景下，我們決定每個檔案放1000條，也就有33個小檔案，也就有33個記憶體隊列，每個隊列取top100條，batch=500時重新整理

硬碟，中轉站存放33*2個數字（因為入中轉站時打上了隊列标記）,最後記憶體活動最大總數為：sum=33*100+500+66=896<1200。

時間複雜度為n*logn。當然這個“閥值”，我們可以再仔細微調。