外排序

　　外部排序的方法

　　外部排序基本上由兩個相互獨立的階段組成。首先，按可用內存大小，將外存上含n個記錄的文件分成若干長度為k的子文件或段(segment)，依次讀入內存并利用有效的內部排序方法對它們進行排序，并將排序后得到的有序子文件重新寫入外存。通常稱這些有序子文件為歸并段或順串;然后，對這些歸并段進行逐趟歸并，使歸并段(有序子文件)逐漸由小到大，直至得到整個有序文件為止。

　　顯然，第一階段的工作已經討論過。以下主要討論第二階段即歸并的過程。先從一個例子來看外排序中的歸并是如何進行的?

　　假設有一個含 10000 個記錄的文件，首先通過10次內部排序得到10個初始歸并段 R1～R10 ，其中每一段都含1000個記錄。然后對它們作如圖10.11所示的兩兩歸并，直至

　　得到一個有序文件為止。

　　將兩個有序段歸并成一個有序段的過程，若在內存中進行，則很簡單，前面討論的2-路歸并排序中的Merge函數便可實現此歸并。但是，在外部排序中實現兩兩歸并時，不僅要調用Merge函數，而且要進行外存的讀/寫，這是由于我們不可能將兩個有序段及歸并結果同時放在內存中的緣故。對外存上信息的讀/寫是以“物理塊”為單位。假設在上例中每個物理塊可以容納200個記錄，則每一趟歸并需進行50次“讀”和50次“寫”，四趟歸并加上內部排序時所需進行的讀/寫，使得在外排序中總共需進行500次的讀/寫。

　　一般情況下，外部排序所需總時間=內部排序(產生初始歸并段)所需時間 m*tis+外存信息讀寫的時間 d*tio +內部歸并排序所需時間 s*utmg

　　其中：tis是為得到一個初始歸并段進行的內部排序所需時間的均值;tio是進行一次外存讀/寫時間的均值;utmg是對u個記錄進行內部歸并所需時間;m為經過內部排序之后得到的初始歸并段的個數;s為歸并的趟數;d為總的讀/寫次數。由此，上例10000個記錄利用2-路歸并進行排序所需總的時間為：

　　10*tis+500*tio+4*10000tmg

　　其中tio取決于所用的外存設備，顯然，tio較tmg要大的多。因此，提高排序效率應主要著眼于減少外存信息讀寫的次數d。

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總