软考软件设计师专题讲义九：数据结构相关算法

　　二路归并排序

　　二路归并排序的基本操作是将两个有序表合并为一个有序表。

　　设r[u…t]由两个有序子表r[u…v-1]和r[v…t]组成，两个子表长度分别为v-u、t-v+1。合并方法为：

　　⑴ i=u;j=v;k=u; //置两个子表的起始下标及辅助数组的起始下标

　　⑵ 若i>v 或 j>t，转⑷ //其中一个子表已合并完，比较选取结束

　　⑶ //选取r[i]和r[j]关键码较小的存入辅助数组rf

　　如果r[i].key

　　否则，rf[k]=r[j]; j++; k++; 转⑵

　　⑷ //将尚未处理完的子表中元素存入rf

　　如果i

　　如果j<=t，将r[i…v]存入rf[k…t] //后一子表非空

　　⑸ 合并结束。

　　【算法10.11】

　　void Merge(ElemType *r，ElemType *rf，int u，int v，int t)

　　{

　　for(i=u，j=v，k=u;i

　　{ if(r[i].key

　　{ rf[k]=r[i];i++;}

　　else

　　{ rf[k]=r[j];j++;}

　　}

　　if(i

　　if(j<=t) rf[k…t]=r[j…t];

　　}

　　两路归并的迭代算法：1个元素的表总是有序的。所以对n个元素的待排序列，每个元素可看成1个有序子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。

　　【算法10.12】

　　void MergeSort(S_TBL *p，ElemType *rf)

　　{ /*对*p表归并排序，*rf为与*p表等长的辅助数组*/

　　ElemType *q1，*q2;

　　q1=rf;q2=p->elem;

　　for(len=1;lenlength;len=2*len) /*从q2归并到q1*/

　　{ for(i=1;i+2*len-1<=p->length;i=i+2*len)

　　Merge(q2，q1，i，i+len，i+2*len-1); /*对等长的两个子表合并*/

　　if(i+len-1length)

　　Merge(q2，q1，i，i+len，p->length); /*对不等长的两个子表合并*/

　　else if(i<=p->length)

　　while(i<=p->length) /*若还剩下一个子表，则直接传入*/

　　q1[i]=q2[i];

　　q1<-->q2; /*交换，以保证下一趟归并时，仍从q2归并到q1*/

　　if(q1!=p->elem) /*若最终结果不在*p表中，则传入之*/

　　for(i=1;i<=p->length;i++)

　　p->elem[i]=q1[i];

　　}

　　}

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