春招的時(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ō)了一下我的想法?，F(xiàn)在再來(lái)看書里關(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ī)的外部訪問(wèn)是非常慢的（相對(duì)比從內(nèi)存讀數(shù)據(jù)），如果使用和“把數(shù)據(jù)全部讀入內(nèi)存然后排序”相同的算法，再加上外部存儲(chǔ)例如磁帶是只能順序訪問(wèn)，那么任何算法都需要(N^2)次外部數(shù)據(jù)訪問(wèn)，將是非?？膳碌暮臅r(shí)。所以需要有專門用于外部排序的算法。
- 第一部分：介紹基于歸并排序的簡(jiǎn)單算法
- 第二部分：在簡(jiǎn)單算法的基礎(chǔ)上讓其支持多路歸并可以提高效率
- 第三部分：首先在簡(jiǎn)單算法上應(yīng)用多相合并，可以節(jié)約外部存儲(chǔ)的空間，然后擴(kuò)展到多路歸并上
- 第四部分：針對(duì)用于歸并的順串進(jìn)行改造，在特定的情況下可以提高算法效率。
簡(jiǎn)單算法
使用歸并排序的思想，簡(jiǎ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盤磁帶，每次將順串的長(zhǎng)度擴(kuò)充為原來(lái)的k倍。在合并的時(shí)候，在k個(gè)元素中發(fā)現(xiàn)最小值是比二路合并復(fù)雜的地方，可以使用優(yōu)先隊(duì)列。多路合并和二路合并區(qū)別不大，就不舉例子了。k路合并需要的趟數(shù)是：
多相合并
在上面的多路合并中，k-路合并需要2k盤磁帶。使用多相合并后，只使用2k-1盤磁帶也可以達(dá)到相同的效果，可以節(jié)省外部存儲(chǔ)空間。下面看如何用三盤磁帶完成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è)空的磁帶上。
可以優(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ǔ)磁帶。
將上面三盤磁帶完成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ù)。
