整理自《數(shù)據(jù)結(jié)構(gòu)高分筆記》

1、概念和流程

基本概念
所謂外部排序，即對(duì)外存中的記錄進(jìn)行排序（相對(duì)于內(nèi)部排序而言），有了內(nèi)部排序算法，為什么還需要外部排序？因?yàn)橥獯嬷杏涗浺?guī)模太大，內(nèi)存放不下。外部排序可以概括為一句話：將內(nèi)存作為工作空間回來輔助外存數(shù)據(jù)的排序。

流程解析
外部排序最常用的算法是歸并排序，是因?yàn)樗恍枰獙⑷康挠涗浂甲x入內(nèi)存就可以完成排序，因此，可以解決由于內(nèi)存空間不足導(dǎo)致的無法對(duì)大規(guī)模記錄進(jìn)行排序的問題。

1）將這組記錄假設(shè)為n個(gè)，分為m個(gè)規(guī)模較小的記錄段（記錄段的長(zhǎng)度不一定相等），并對(duì)這些小記錄段進(jìn)行排序，一般情況下這些記錄段都足夠小，可以整段讀入內(nèi)存并選擇合適的排序算法對(duì)其排序。

2）將m個(gè)有序記錄每k個(gè)分為一組，得到ceil（m／k）組記錄段，取其中一組，假設(shè)k=5，如下圖所示，每行一段，將每段的段首的記錄讀入內(nèi)存，如圖中灰色的所示：

3）用某種方法從讀入內(nèi)存的這組記錄中選出最小的，比如下面我們選擇1.

4）將上一步選出的最小值寫回外存，并將其所在記錄段的次小值讀入內(nèi)存補(bǔ)上空位置，如圖：

5）重復(fù)以上過程

6）當(dāng)此組記錄全部導(dǎo)出之后，就會(huì)在外存中得到一個(gè)較長(zhǎng)的有序記錄段。以此方法將剩下的所有組記錄段都?xì)w并成為較長(zhǎng)的記錄段，就得到了ceil(m/k)個(gè)較長(zhǎng)的有序記錄段，然后按照上面同樣的方法分組、歸并、排序，并重復(fù)此過程，就可以完成對(duì)這n個(gè)記錄的排序。