[ 資料結構 小學堂 ] 排序 : 直接合併排序法

前言 :
當我們所要排序的資料量太大或檔案太大, 無法直接在記憶體內排序, 而須依賴外部儲存裝置時, 我們就會使用到外部排序法. 外部儲存裝置又可依照存取方式分為兩種, 如循序存取 (磁帶) 或隨機存取 (如磁碟). 要循序存取的檔案就像是串列一樣, 我們必須事先走訪整個串列才有辦法進行排序, 而隨機存取的檔案就像是陣列, 資料存取方便所以相對的排序也會比循序存取快一點, 一般來說外部排序法最常使用的就是合併排序法.

直接合併排序法 :
直接合併排序法 (Direct Merge Sort) 是外部儲存裝置最常用的排序方法, 它可以分成兩個步驟 :

1. 將欲排序的檔案分為幾個可以載入記憶體空間大小的檔案, 再使用內部排序法將各檔案內的資料排序.
2. 將第一步驟所建立的小檔案每兩個合併成一個檔案. 兩兩合併後, 把所有檔案合併成一個檔案後就可以完成排序.

例如 : 我們第一步把一個檔案分成6個小檔案 :

小檔案都完成排序後, 兩兩合併成一個較大的檔案, 最後再合併成一個檔案即可完成.

接著以一個實際範例說明, 假設我們要對一個檔案 test.txt 進行排序, 而 test.txt 裡包含 1500 筆資料, 但記憶體最多一次只能處理 300筆資料 :
步驟一 : 將 test.txt 分成五個檔案 t1~t5, 每個檔案300筆.
步驟二 : 以內部排序法對 t1~t5 進行排序.
步驟三 : 進行檔案 t1, t2 合併, 將記憶體分成三部分, 每部分可存放100筆資料, 先把 t1 及 t2 的前100筆資料放到記憶體裡, 排序後放到合併完成緩衝區, 等到緩衝區滿了之後便寫入磁碟 .
步驟四 : 重複步驟三直到完成為止.
合併的方法如下 :
假設我們有兩個完成排序的檔案要合併, 排序由小到大 :

a1: 1,4,6,8,9
a2: 2,3,5,7

首先在兩個檔案中分別讀出一個元素進行比較, 比較後將較小的檔案放入合併緩衝區內.
Step1 : 1與2 比較後將較小的1放進緩衝區, a1 的檔案指標往後一個元素.

Step2 : 2與4 比較後將較小的2放進緩衝區, b1 的檔案指標往後一個元素.

Step3 : 3與4 比較後將較小的3放進緩衝區, b1 的檔案指標往後一個元素.

Step4 : 4與5 比較後將較小的4放進緩衝區, a1 的檔案指標往後一個元素.

依此類推, 等到緩衝區的資料滿了就進行寫入檔案的動作; a1 或 b1 的檔案指標到了最後一筆就讀取剩下的資料完成排序.

範例代碼 :

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include   
4. #include   
5.   
6. using namespace std;  
7. void mergeSort(ofstream& fp, ifstream& fp1, ifstream& fp2) {  
8.     char n1,n2;  
9.     char txt1[40];  
10.     char txt2[40];  
11.     fp1>>n1;  
12.     fp2>>n2;  
13.     while(fp1.eof()==0 && fp2.eof()==0) {  
14.         if(n1 <= n2) {  
15.             fp.put(n1);  
16.             fp1 >> n1; /*繼續下筆 n1資料*/  
17.         } else {  
18.             fp.put(n2);  
19.             fp2 >> n2; /*繼續下筆 n2資料*/  
20.         }  
21.     }  
22.     if(fp1.eof()) {  
23.         while(!fp2.eof()) {  
24.             fp2>>n2;  
25.             fp.put(n2);  
26.         }  
27.     } else if(fp2.eof()) {  
28.         while(!fp1.eof()) {  
29.             fp1 >> n1;  
30.             fp.put(n1);  
31.         }  
32.     }  
33. }  
34. void main() {  
35.     char *data1Path = "E:/MS-VSProj/DataStructureExam/Data/data1.txt";  
36.     char *data2Path = "E:/MS-VSProj/DataStructureExam/Data/data2.txt";  
37.     char *dataPath = "E:/MS-VSProj/DataStructureExam/Data/data.txt";  
38.     char txt[40];  
39.     ofstream fp;  
40.     ifstream fp1, fp2;  
41.     ifstream f,f1,f2;  
42.     fp.open(dataPath, ios::out);  
43.     fp1.open(data1Path, ios::in);  
44.     fp2.open(data2Path, ios::in);  
45.     if(!fp.is_open()) {  
46.         cout << "開啟檔案 data.txt 失敗!" << endl;  
47.     } else if(!fp1.is_open()) {  
48.         cout << "開啟檔案 data1.txt 失敗!" << endl;  
49.     } else if(!fp2.is_open()) {  
50.         cout << "開啟檔案 data2.txt 失敗!" << endl;  
51.     } else {  
52.         cout << "資料排序中..." << endl;  
53.         mergeSort(fp, fp1, fp2);  
54.         cout << "資料排序完成!!" << endl;  
55.     }  
56.     fp.close();  
57.     fp1.close();  
58.     fp2.close();  
59.     cout << "data1.txt 資料內容為: " << endl;  
60.     f1.open(data1Path, ios::in);  
61.     while(!f1.eof()) {  
62.         f1 >> txt;  
63.         cout << txt << endl;  
64.     }  
65.     cout << "data2.txt 資料內容為: " << endl;  
66.     f2.open(data2Path, ios::in);  
67.     while(!f2.eof()){  
68.         f2 >> txt;  
69.         cout << txt << endl;  
70.     }  
71.     cout << "排序後 data.txt 資料為: " << endl;  
72.     f.open(dataPath, ios::out);  
73.     while(!f.eof()) {  
74.         f >> txt;  
75.         cout << txt << endl;  
76.     }  
77.     f.close();  
78.     f1.close();  
79.     f2.close();  
80. }  

執行結果 :

資料排序中...
資料排序完成!!
data1.txt 資料內容為:
13578
data2.txt 資料內容為:
2469
排序後 data.txt 資料為:
123456789

補充說明 :
* Algorithm Gossip: 合併排序法

合併排序法基本是將兩筆已排序的資料合併並進行排序，如果所讀入的資料尚未排序，可以先利用其它的排序方式來處理這兩筆資料，然後再將排序好的這兩筆資料合併。
有人問道，如果兩筆資料本身就無排序順序，何不將所有的資料讀入，再一次進行排序？排序的精神是儘量利用資料已排序的部份，來加快排序的效率，小筆資料的 排序較為快速，如果小筆資料排序完成之後，再合併處理時，因為兩筆資料都有排序了，所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率...

This message was edited 6 times. Last update was at 06/06/2010 13:44:27