軟考軟件設計師專題講義十：常用的算法設計方法

　　2.2 歸并排序

　　歸并排序：是通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度;歸并排序的基本思想是：將兩個或兩個以上的有序子序列“歸并”為一個有序序列。

　　在內部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的有序子序列 歸并為一個有序序列。

　　“歸并”算法描述如下：

　　template

　　void Merge (Elem SR[], Elem TR[], int i, int m, int n) {

　　// 將有序的SR[i..m]和SR[m+1..n]歸并為

　　// 有序的TR[i..n]

　　for (j=m+1, k=i; i<=m && j<=n; ++k)

　　{ // 將SR中記錄由小到大地并入TR

　　if (SR.key<=SR[j].key) TR[k] = SR[i++];

　　else TR[k] = SR[j++];

　　}

　　if (i<=m) TR[k..n] = SR[i..m];

　　// 將剩余的SR[i..m]復制到TR

　　if (j<=n) TR[k..n] = SR[j..n];

　　// 將剩余的SR[j..n]復制到TR

　　} // Merge

　　歸并排序的算法可以有兩種形式：遞歸的和遞推的，它是由兩種不同的程序設計思想得出的。在此，只討論遞歸形式的算法。

　　這是一種自頂向下的分析方法：

　　如果記錄無序序列R[s..t]的兩部分]û(s+t)/2ëR[s..和û(s+t)/2+1..tëR[分別按關鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列，由此，應該先分別對這兩部分進行2-路歸并排序。

　　template

　　void Msort ( Elem SR[], Elem TR1[], int s, int t ) {

　　// 將SR[s..t]進行2-路歸并排序為TR1[s..t]。

　　if (s==t) TR1[s] = SR[s];

　　else {

　　m = (s+t)/2;

　　// 將SR[s..t]平分為SR[s..m]和SR[m+1..t]

　　Msort (SR, TR2, s, m);

　　// 遞歸地將SR[s..m]歸并為有序的TR2[s..m]

　　Msort (SR, TR2, m+1, t);

　　//遞歸地SR[m+1..t]歸并為有序的TR2[m+1..t]

　　Merge (TR2, TR1, s, m, t);

　　// 將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]

　　}

　　} // MSort

　　template

　　void MergeSort (Elem R[]) {

　　// 對記錄序列R[1..n]作2-路歸并排序。

　　MSort(R, R, 1, n);

　　} // MergeSort

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