軟考軟件設(shè)計師專題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　外排序

　　外部排序的方法

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

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

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

　　得到一個有序文件為止。

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

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

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

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

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

　　　　　　　計算機(jī)軟考軟件設(shè)計師練習(xí)試題及答案解析匯總