春招的時(shí)候在某養(yǎng)豬場(chǎng)面試搁嗓，面試官問(wèn)了一個(gè)問(wèn)題：“如何用256M內(nèi)存的機(jī)器對(duì)一個(gè)2G的數(shù)據(jù)進(jìn)行排序”腺逛。之前沒(méi)看過(guò)這方面的內(nèi)容衡怀，想了一下說(shuō)用歸并排序，然后簡(jiǎn)略的說(shuō)了一下我的想法∨籽睿現(xiàn)在再來(lái)看書(shū)里關(guān)于外部排序的內(nèi)容怖现，當(dāng)時(shí)的大方向沒(méi)錯(cuò)，但是剩下的具體實(shí)現(xiàn)真竖、外部空間復(fù)雜度計(jì)算、時(shí)間復(fù)雜度計(jì)算和優(yōu)化等都沒(méi)考慮到位战秋。
因?yàn)橛?jì)算機(jī)的外部訪(fǎng)問(wèn)是非常慢的（相對(duì)比從內(nèi)存讀數(shù)據(jù)）讨韭，如果使用和“把數(shù)據(jù)全部讀入內(nèi)存然后排序”相同的算法癣蟋，再加上外部存儲(chǔ)例如磁帶是只能順序訪(fǎng)問(wèn)疯搅，那么任何算法都需要(N^2)次外部數(shù)據(jù)訪(fǎng)問(wèn)埋泵，將是非常可怕的耗時(shí)丽声。所以需要有專(zhuān)門(mén)用于外部排序的算法。
- 第一部分：介紹基于歸并排序的簡(jiǎn)單算法
- 第二部分：在簡(jiǎn)單算法的基礎(chǔ)上讓其支持多路歸并可以提高效率
- 第三部分：首先在簡(jiǎn)單算法上應(yīng)用多相合并雁社，可以節(jié)約外部存儲(chǔ)的空間，然后擴(kuò)展到多路歸并上
- 第四部分：針對(duì)用于歸并的順串進(jìn)行改造磺浙，在特定的情況下可以提高算法效率徒坡。
簡(jiǎn)單算法
使用歸并排序的思想，簡(jiǎn)單的雙路歸并需要四盤(pán)磁帶（就是外部存儲(chǔ)）呵曹。最初的數(shù)據(jù)在T_a1上何暮，內(nèi)存為M，就是每次可以使用排序算法對(duì)M個(gè)數(shù)據(jù)進(jìn)行排序跨新。
- 依次從T_a1上讀入M數(shù)據(jù)坏逢，進(jìn)行排序。
- 然后交替的輸出到T_b1和T_b2上肖揣。每組排過(guò)序的記錄叫做一個(gè)順串浮入。
- 將 T_b1和T_b2的第一個(gè)順串取出來(lái)將兩者合并（過(guò)程參考?xì)w并算法），將結(jié)果輸出到T_a1上彤断。
- 繼續(xù)上一個(gè)步驟，交替的輸出到T_a1和T_a2上宰衙。直到T_b1或T_b2為空。如果剩下一個(gè)順串一屋，拷貝到適當(dāng)?shù)拇艓稀?/li>
- 這樣我們?cè)赥_a1和T_a2上得到長(zhǎng)度為M的順串劲蜻，重復(fù)上面的過(guò)程考余，知道得到長(zhǎng)度為N的順串楚堤。
示例：
初始狀態(tài)：
| T_a1 | 81 94 11 96 12 35 17 99 28 58 41 75 15 |
|---|---|
| T_a2 | |
| T_b1 | |
| T_b2 |
第1，第2步之后：
| T_a1 | |||
|---|---|---|---|
| T_a2 | |||
| T_b1 | 11 81 94 | 17 28 99 | 15 |
| T_b2 | 12 35 96 | 41 58 75 |
第3衅胀，第4步之后：
| T_a1 | 11 12 35 81 94 96 | 15 |
|---|---|---|
| T_a2 | 17 28 41 58 75 99 | |
| T_b1 | ||
| T_b2 |
重復(fù)這個(gè)從Ta1 Ta2歸并到Tb1 Tb2酥筝，從Tb1 Tb2歸并到Ta1 Ta2的過(guò)程：
| T_a1 | |
|---|---|
| T_a2 | |
| T_b1 | 11 12 17 28 35 51 58 75 81 94 96 99 |
| T_b2 | 15 |
| T_a1 | 11 12 15 17 28 35 51 58 75 81 94 96 99 |
|---|---|
| T_a2 | |
| T_b1 | |
| T_b2 |
完成！
我們“從Ta1 Ta2歸并到Tb1 Tb2掸掏，從Tb1 Tb2歸并到Ta1 Ta2”這個(gè)過(guò)程用了3趟宙帝。因?yàn)榈谝淮雾槾拈L(zhǎng)度為M，在二路歸并的情況下愿待，每次將順串的長(zhǎng)度延長(zhǎng)一倍靴患，需要次數(shù)為：
多路合并
上面的簡(jiǎn)單算法就是二路合并，我們將其擴(kuò)展到一般狀態(tài)——k路合并访圃。
k路合并需要2k盤(pán)磁帶相嵌，每次將順串的長(zhǎng)度擴(kuò)充為原來(lái)的k倍况脆。在合并的時(shí)候批糟，在k個(gè)元素中發(fā)現(xiàn)最小值是比二路合并復(fù)雜的地方徽鼎，可以使用優(yōu)先隊(duì)列。多路合并和二路合并區(qū)別不大否淤，就不舉例子了石抡。k路合并需要的趟數(shù)是：
多相合并
在上面的多路合并中，k-路合并需要2k盤(pán)磁帶嚎京。使用多相合并后隐解，只使用2k-1盤(pán)磁帶也可以達(dá)到相同的效果，可以節(jié)省外部存儲(chǔ)空間煞茫。下面看如何用三盤(pán)磁帶完成2-路合并：
- T_1上有34個(gè)順串長(zhǎng)度的數(shù)據(jù)续徽，可以選擇排序后在T_2、T_3上分別輸出17個(gè)順串炸宵。
- 合并輸出到T _1上土全，T_1上有17個(gè)順串。
- 將8個(gè)順串從T_1拷貝到T_2上裹匙，然后合并到T_3上概页，這時(shí)候T_3有9個(gè)順串。
- 每次拷貝二分之一個(gè)順串到一個(gè)空的磁帶上，然后合并到剩下的那個(gè)空的磁帶上铃将。
可以?xún)?yōu)化一下哑梳，讓每次合并完成之后天然形成兩個(gè)磁帶有順串，一個(gè)為空的情景：
- 把T_1上的數(shù)據(jù)排序后悯仙，把21個(gè)順串放到T_2上面吠卷，13個(gè)放到T_3上。
- 合并之后祭隔，T_3為空，T_1上有13個(gè)順串茴她，T_2上有8個(gè)順串程奠。
- 合并祭钉，T_2空，T_3上有8個(gè)順串距境，T_1上有5個(gè)垮卓。重復(fù)這個(gè)過(guò)程。
第一步分配的策略是：如果總順串的數(shù)量是斐波那契數(shù)F_N,那么將順串分解成F(N-1)和 F(N-2)诬滩。如果不是斐波那契數(shù)灭将，需要用一些啞順串(dummy run)來(lái)填補(bǔ)磁帶。
將上面三盤(pán)磁帶完成2-路合并擴(kuò)展到k-路的多相合并空镜，順串分解使用k階斐波那契數(shù)列：
5階斐波那契數(shù)列就是：
0，0张抄，0洼怔，0，1泽台，1矾缓，2，4蜕依，8琉雳，16，31檐束，61……
替換選擇
上面的排序算法中束倍，第一步順串的生成都使用了常規(guī)內(nèi)存排序的方法，每次可以生成和內(nèi)存容量一樣大的有序數(shù)列甥桂。在替換選擇算法中邮旷，無(wú)序數(shù)列平均可以生成2M長(zhǎng)度的順串。
- M個(gè)數(shù)據(jù)被讀入內(nèi)存办陷，并放到一個(gè)優(yōu)先隊(duì)列中狡孔。執(zhí)行一次DeleteMin把最小記錄輸出到磁帶上。
- 內(nèi)存空出一個(gè)位置殃恒，在從磁帶讀入下一個(gè)記錄，如果比剛剛輸出的數(shù)據(jù)要大离唐，放入優(yōu)先隊(duì)列亥鬓。否則把這個(gè)新元素存入優(yōu)先隊(duì)列的死區(qū)(dead space)。
- 重復(fù)上一個(gè)步驟覆积，直到優(yōu)先隊(duì)列的大小為0熟呛，結(jié)束第一個(gè)順串的構(gòu)造。
- 使用死區(qū)中的所有元素建立一個(gè)新的優(yōu)先隊(duì)列吗冤，重復(fù)1九府，2，3的過(guò)程侄旬。
替換選擇在一些情況下勾怒，如果說(shuō)大部分的數(shù)都是逆序的声旺，效果并不比表標(biāo)準(zhǔn)算法好。但是鉴扫，如果輸入數(shù)據(jù)是大致順序的澈缺，那么可以第一步就產(chǎn)生很長(zhǎng)的順串，減少來(lái)回歸并的趟數(shù)莱预。
