外部排序指的是大檔案的排序，即待排序的記錄存儲在外存儲器上，待排序的檔案無法一次裝入記憶體，需要在記憶體和外部存儲器之間進行多次數據交換，以達到排序整個檔案的目的。
基本介紹
規則種類,外部排序,初始順串,合併排序,其他算法,最佳化性能,內部排序,
規則種類
排序是電腦程式設計中的一種重要操作，它的功能是將任意序列的數據元素或記錄重新按關鍵字順序排列成有序的序列。 有序序列為記錄的查找、插入和刪除提供了方便，可以有效提高搜尋效率。因此，研究各類排序方法是計算機研究中的重要課題之一。根據待排序記錄數量及其在排序過程中涉及的存儲器，可將排序方法分為兩大類: 一類是內部排序, 指的是待排序記錄存放在計算機存儲器中進行的排序過程；另一類是外部排序, 指的是待排序記錄的數量很大，以至於記憶體一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。
外部排序指的是大檔案的排序，當待排序的檔案很大時，無法將整個檔案的所有記錄同時調入記憶體進行排序，只能將檔案存放在外存，這種排稱為外部排序。外部排序的過程主要是依據數據的內外存交換和“內部歸併”兩者結合起來實現的。
一般提到排序都是指內排序，比如快速排序，堆排序，歸併排序等，所謂內排序就是可以在記憶體中完成的排序。RAM的訪問速度大約是磁碟的25萬倍，我們當然希望如果可以的話都是內排來完成。但對於大數據集來說，記憶體是遠遠不夠的，這時候就涉及到外排序的知識了。
外部排序最常用的算法是多路歸併排序，即將原檔案分解成多個能夠一次性裝入記憶體的部分分別把每一部分調入記憶體完成排序。然後，對已經排序的子檔案進行歸併排序。
外部排序
一般來說外排序分為兩個步驟：預處理和合併排序。首先，根據可用記憶體的大小，將外存上含有n個紀錄的檔案分成若干長度為t的子檔案（或段）；其次，利用內部排序的方法，對每個子檔案的t個紀錄進行內部排序。這些經過排序的子檔案（段）通常稱為順串(run)，順串生成後即將其寫入外存。這樣在外存上就得到了m個順串（m=[n/t]）。最後，對這些順串進行歸併，使順串的長度逐漸增大，直到所有的待排序的記錄成為一個順串為止。
初始順串
預處理階段最重要的事情就是選擇初始順串。通常使用的方法為置換選擇排序，它是堆排序的一種變形，實現思路同STL的partial_sort。步驟如下：
（1）初始化堆
從磁碟讀入M個記錄放到數組RAM中；
設定堆末尾標準LAST=M-1；
建立最小值堆。
（2）重複以下步驟直到堆為空
把具有最小關鍵碼值的記錄Min也就是根節點送到輸出緩衝區；
設R是輸入緩衝區中的下一條記錄，如果R的關鍵碼大於剛剛輸出的關鍵碼值Min，則把R放到根節點，否則使用數組中LAST位置的記錄代替根節點，並將剛才的R放入到LAST所在位置，LAST=LAST-1；
（3）重新排列堆，篩出根節點。
如果堆的大小是M,一個順串的最小長度就是M個記錄，因為至少原來在堆中的那些記錄將成為順串的一部分，如果輸入時逆序的，那么順串的長度只能是M，最好情況輸入是正序的，有可能一次性就能把整個檔案生成一個順串，由此可見生成順串的長度是大小不一的，但是每個順串卻是有序的，利用掃雪機模型能夠得到平均順串的長度為2M。
外部排序最常用的算法是多路歸併排序，即將原檔案分解成多個能夠一次性裝入記憶體的部分，分別把每一部分調入記憶體完成排序。然後，對已經排序的子檔案進行歸併排序。
合併排序
（1） 二路合併排序
二路合併是最簡單的合併方法，合併的實現與內排序中的二路歸併算法並無本質區別，下面通過具體例子，分析二路合併外部排序的過程。
有一個含有9000個紀錄的檔案需要排序（基於關鍵字）。假定系統僅能提供容納1800個紀錄的記憶體。檔案在外存（如磁碟）上分塊存儲，每塊600個紀錄。外部排序的過程分為生成初始順串和對順串進行歸併排序兩個階段。在生成初始順串階段，每次讀入1800個紀錄（即3段）待記憶體，採用內排序依次生成順串依次寫入外存儲器中。
順串生成後，就開一開始對順串進行歸併。首先將記憶體等分成3個緩衝區，每個緩衝區可容納600個紀錄，其中兩個為輸入緩衝區，一個為輸出緩衝區，每次從外存讀入待歸併的塊到輸入緩衝取，進行內部歸併，歸併後的結果送入輸出緩衝區，輸出緩衝區的記錄寫滿時再將其寫入外存。若輸入緩衝區中的紀錄為空，則將待歸併順串中的後續塊讀入輸入緩衝區中進行歸併，直到待歸併的兩個順串都已歸併為止。重複上述的歸併方法，由含有5塊（每塊上限1800個記錄）的順串經二路歸併的一遍歸併後生成含有3塊（每塊上限3600個記錄）的順串，再經過第二遍……第s遍（s=[]，m為初始順串的個數），生成含有所有記錄的順串，從而完成了二路歸併外部排序。
對檔案進行外部排序的過程中，因為對外存的讀寫操作所用的操作的時間遠遠超過在記憶體中產生順串和合併所需的時間，所以常用對外存的讀寫操作所用的時間作為外部排序的主要時間開銷。分析一下上述二路歸併排序的對外存的讀寫時間。初始時生成5個順串的讀寫次數為30次(每塊的讀寫次數為2次)。
類似地，可得到二路、三路……多路合併方法。
（2） 多路替代選擇合併排序
採用多路合併技術，可以減少合併遍數，從而減少塊讀寫次數，加快排序速度。但路數的多少依賴於記憶體容量的限制。此外，多路合併排序的快慢還依賴於內部歸併算法的快慢。
設檔案有n個紀錄，m個初始順串，採用k路合併方法，那么合併階段將進行遍合併。k路合併的基本操作是從k個順換的第一個紀錄中選出最小紀錄（即關鍵字最小的紀錄），把它從輸入緩衝區移入輸出緩衝區。若採用直接選擇方式選擇最小元，需要k-1次比較，遍合併共需n(k-1)=次比較。由於隨k的增長而增長，則內部歸併時間亦隨k的增大而增大，這將抵消由於增大k而減少外存信息讀寫時間所得的效果。若在k個紀錄中採用樹形選擇方式選擇最小元，則選擇輸出一個最小元之後，只需從某葉到根的路徑上重新調整選擇樹，即可選擇下一個最小元。重新構造選擇書僅用O()次比較，於是內部合併時間O(n)=O(),它與k無關，不再隨k的增大而增大。
常見的有基於“敗者樹”的多路替代選擇合併排序方法。
其他算法
最佳化性能
計算機科學家吉姆·格雷的SortBenchmark網站用不同的硬體、軟體環境測試了實現方法不同的多種外排序算法的效率。效率較高的算法具有以下的特徵：
- 並行計算
- 用多個磁碟驅動器並行處理數據，可以加速順序磁碟讀寫。
- 在計算機上使用多執行緒，可在多核心的計算機上得到最佳化。
- 使用異步輸入輸出，可以同時排序和歸併，同時讀寫。
- 使用多台計算機用高速網路連線，分擔計算任務。
提高硬體速度
提高軟體速度
- 對於某些特殊數據，在第一階段的排序中使用基數排序。
- 壓縮輸入輸出檔案和臨時檔案。
內部排序
考慮到外部排序涉及的待排序記錄數量大，可以採取分治的思想(即先分解, 再遞歸求解, 然後合併) 將其劃分成幾段合適的待排序記錄，然後對每一小段採用內部排序方法。換句話說，就是將外部排序轉化為內部排序，所以為了進一步研究外部排序, 需先對內部排序進行深入的討論。如果在排序過程中依據不同原則對內部排序方法進行分類，則大致可分為插入排序、冒泡排序、選擇排序、歸併排序和快速排序等5類。
通常, 排序記錄存儲具有如下3種形式:
1、待排序的一組記錄存放在地址連續的一組存儲單元上，它類似於線性表的順序存儲結
構，在序列中相鄰的2個記錄Rj 和R j+ 1 ( j = 1， 2，……， n - 1) 其存儲位置也相鄰。這種存儲方式中，記錄之間的次序關係由其存儲的位置決定，排序通過移動記錄來實現。
2、一組待排序記錄存放在靜態鍊表中，記錄之間的次序關係由指針指示, 則實現排序不需要移動記錄，僅需移動指針即可。
3、待排序記錄本身存儲在一組地址連續的存儲單元內, 同時另設一個指示各個記錄存儲位
置的地址向量, 在排序過程中不移動記錄本身,而移動地址向量中這些記錄的 地址, 在排序結束之後再按照地址向量中的值調整記錄的存儲位置。
