软考软件设计师专题讲义十：常用的算法设计方法

　　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

　　　　　　　计算机软考软件设计师练习试题及答案解析汇总