漫畫，什么是外部排序
還記得面試現場第一篇文章【面試現場】如何判斷一個數是否在40億個整數中？發出之后，最后蛋哥說把40億個數先進行外部排序，有讀者問到，記憶體無法一次性加載40億個數，如何排序？
背景
西天取經的路上，一樣上演著編程的樂趣.....
(互聯網偵察注：160億位元組大概是16G吧，20億int32大概8G)
置換選擇
例如我們可以從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如下：
這種方法適合要排序的資料太多，以至于記憶體一次性裝載不下，只能通過把資料分幾次的方式來排序，我們也把這種方法稱之為外部排序
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/65008.html
標籤：C