西天取經的路上，一樣上演著編程的樂趣.....

? ??

? ? ?

? ? ?

? ?排序的時候我們可以選擇快速排序或歸并排序等算法。

? ?為了方便，我們把排序好的2G有序數據稱之為有序子串吧。接著我們可以把兩個小的有序子串合并成一個大的有序子串。

? ? ? ?

? ? 按照這個方法來回合并，總共經過三次合并之后就可以得到8G的有序子串。

? ? ?

? ? ?

? ?接下來把12個數據分成4份，然后排序成有序子串。

? ? ? ??

? ?然后把子串進行兩兩合并。

? ? ? ? ? ??

? ?輸出哪個元素，就在哪個元素所在的有序子串再次讀入一個元素。

? ? ? ? ? ? ? ?

? ?繼續

? ? ? ? ? ??

? ? 重復直到合并成一個包含6個int的有序子串。

? ? ? ? ? ? ? ? ?

? ? 再把兩個包含6個int的有序子串合并成一個包含12個int數據的最終有序子串。

? ? ? ? ? ? ? ? ??

? ? 然后就合并完成了。

? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 優化策略

? ?? ? ? ? ??

? 解釋下:例如對于數據2,我們把無序的12個數據分成有序的4個子串需要讀寫各一次，把2份3個有序子串合并成6個有序子串各一次;把2份6個有序子串合并從12個有序子串讀寫各一次，一共需要讀寫各3次。

? ? ? ? ? ? ? ? ??

? ? ? ? ? ??? ? ? ?

? ? ? ? ? ? ? ????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?多路歸并

? ? ?為了方便講解，我們假設內存一共可以裝4個int型數據。

? ? ? ? ? ? ?

? ? ? ??

? ? ? ?

? ? ?? ? ? ? ?

? ? ? ?? ? ? ? ? ? ? ?

? ? ? ? ? ?? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 置換選擇

? ? ??? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ??

? ? ? 例如我們可以從12個數據讀取3個存到內存中，然后從內存中選出最小的那個數放進子串p1里;

? ? ? 之后再從剩余的9個數據讀取一個放到內存中，然后再從內存中選出一個數放進子串p1里，這個數必須滿足比p1中的其他數大，且在內存中盡量小。

? ? ? ?這樣一直重復，直到內存中的樹都比p1中的數小，這時p1子串存放結束，繼續來p2子串的存放。例如(這時假設內存只能存放3個int型數據);

? ? ? ?12個無序的int數據:

? ? ? ? ? ? ? ? ? ??

? ? ? ?讀入3個到內存中，且選出一個最小的到子串p1;

? ? ? ? ? ? ? ? ? ??

? ? ? ?從內存中再次讀取一個元素86:

? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ?從內存中再次讀取一個元素3:

? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ?從內存中再次讀取一個元素24:

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? 從內存中再次讀取一個元素8:

? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ?這個時候，已經沒有符合要求的數了，且內存已滿，進而用p2子串來存放，以此類推。

? ? ? ?通過這種方法，p1子串存放了4個數據，而原來的那種方法p1子串只能存放3個數據。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ?從12個數據中讀取3個數據，構建成一個最小堆，然后從堆頂選擇一個數寫入到p1中。

? ? ? ?之后再從剩余的9個數種讀取一個數，如果這個數比剛才那個寫入到p1中的數大，則把這個數插入到最小堆中，重新調整最小堆結構，然后在堆頂選一個樹寫入到p1中。

? ? ? ?否則，把這個數暫放在一邊，暫時不處理。之后一樣需要調整堆結構，從堆頂選擇一個數寫入到p1中。

? ? ? ?這里說明一下，那個被放在一邊的數是不能再放入p1中的了，因為它一定比p1中的數都要小，所以它會放在下一個子串中。

? ? ? 看這些文字會讓人頭大，我畫圖解釋一下吧。

? ? ? 從12數據讀取3個數據:

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? 構建最小堆，且選出目標數:

? ? ? ? ? ? ?

? ? ? ?讀入下一個數86:

? ? ? ? ?

? ? ? ?讀入下一個數3，比70小，暫放一邊，不加入堆結構中:

? ? ? ? ? ? ? ??

? ? ? ?讀入下一個數據24,比81小，不加入堆結構:

? ? ? ? ? ??

? ? ? ? 讀入下一個數據8,比86小，不加入堆結構，此時p1已經完成了，把那些剛才暫放一邊的數重新構成一個堆，繼續p2的存放。

? ? ? ? ?

? ? ? ? 以此類推..........

? ? ? ? 最后生成的p2如下:

? ? ? ? ? ? ? ??

? ? ? ? ?? ? ? ??

? ? ? ? ? ? ?

? ? ? ? ? ?

? ? ? 這種方法適合要排序的數據太多，以至于內存一次性裝載不下。只能通過把數據分幾次的方式來排序，我們也把這種方法稱之為外部排序。

? ? ? ? ? ? ? ? ? ??

總結

以上是生活随笔為你收集整理的漫画: 什么是外部排序?的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。