軟考軟件設(shè)計(jì)師專(zhuān)題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　二路歸并排序

　　二路歸并排序的基本操作是將兩個(gè)有序表合并為一個(gè)有序表。

　　設(shè)r[u…t]由兩個(gè)有序子表r[u…v-1]和r[v…t]組成，兩個(gè)子表長(zhǎng)度分別為v-u、t-v+1。合并方法為：

　�、� i=u;j=v;k=u; //置兩個(gè)子表的起始下標(biāo)及輔助數(shù)組的起始下標(biāo)

　�、� 若i>v 或 j>t，轉(zhuǎn)⑷ //其中一個(gè)子表已合并完，比較選取結(jié)束

　　⑶ //選取r[i]和r[j]關(guān)鍵碼較小的存入輔助數(shù)組rf

　　如果r[i].key

　　否則，rf[k]=r[j]; j++; k++; 轉(zhuǎn)⑵

　　⑷ //將尚未處理完的子表中元素存入rf

　　如果i

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

　�、� 合并結(jié)束。

　　【算法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個(gè)元素的表總是有序的。所以對(duì)n個(gè)元素的待排序列，每個(gè)元素可看成1個(gè)有序子表長(zhǎng)度均為2。再進(jìn)行兩兩合并，直到生成n個(gè)元素按關(guān)鍵碼有序的表。

　　【算法10.12】

　　void MergeSort(S_TBL *p，ElemType *rf)

　　{ /*對(duì)*p表歸并排序，*rf為與*p表等長(zhǎng)的輔助數(shù)組*/

　　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); /*對(duì)等長(zhǎng)的兩個(gè)子表合并*/

　　if(i+len-1length)

　　Merge(q2，q1，i，i+len，p->length); /*對(duì)不等長(zhǎng)的兩個(gè)子表合并*/

　　else if(i<=p->length)

　　while(i<=p->length) /*若還剩下一個(gè)子表，則直接傳入*/

　　q1[i]=q2[i];

　　q1<-->q2; /*交換，以保證下一趟歸并時(shí)，仍從q2歸并到q1*/

　　if(q1!=p->elem) /*若最終結(jié)果不在*p表中，則傳入之*/

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

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

　　}

　　}

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