軟考軟件設(shè)計(jì)師專題講義十：常用的算法設(shè)計(jì)方法

　　2.2 歸并排序

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

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

　　“歸并”算法描述如下：

　　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]復(fù)制到TR

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

　　// 將剩余的SR[j..n]復(fù)制到TR

　　} // Merge

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

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

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

　　template

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

　　// 將SR[s..t]進(jìn)行2-路歸并排序?yàn)門R1[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[]) {

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

　　MSort(R, R, 1, n);

　　} // MergeSort

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