子函数merge()

《子函数merge()》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、合并排序中用到的子函数merge()，功能是合并两个有序的子数组，其算法如下：输入：整数数组A[]，下标p,q,r,元素个数m。A[p]~A[q]及A[q+1]~A[r]已按递增顺序排序输出：按递增顺序排序的子数组A[p]~A[r]题意：合并两个递增子数组A[p]~A[q]及A[q+1]~A[r]，合并后按递增顺序排序。1.voidmerge(intA[],intp,intq,intr,intm)2.{3.int*bp=newint[m]；分配缓冲区，存放被排序的元素4.inti,j,k;5.i=p;j=q+1;k=0;i表示子数组A[p]~A[q]中当前元

2、素所在的位置；j表示子数组A[q+1]~A[r]中当前元素所在的位置6.while(i<=q&&j<=r)表示子数组A[p]~A[q]中当前元素所在的位置以及子数组A[q+1]~A[r]中当前元素所在的位置都没有超过各自的子数组范围7.if(A[i]<=A[j])比较子数组A[p]~A[q]和子数组A[q+1]~A[r]中当前元素的大小8.bp[k++]=A[i++]将较小的元素先装入临时数组bp[]；然后使元素的序列自增，于是下一轮循环就可以比较下一组元素的大小了9.else10.bp[k++]=A[j++];较大的元素后装入临时数组bp[]11.}12.

3、if(i==q+1)如果子数组A[p]~A[q]中的元素已经全部装入临时数组bp[]（先装入的是较小的元素）13.{for(;j<=r;j++)14.bp[k++]=A[j];}那么就将子数组A[q+1]~A[r]中剩下的元素全部装入临时数组bp[]15.else否则一就定是子数组A[q+1]~A[r]中的元素已经全部装入临时数组bp[]（先装入的是较小的元素）16.{for(;i<=q;i++)17.bp[k++]=A[i];}于是，将子数组A[p]~A[q]中剩下的元素全部装入临时数组bp[]18.k=0;为将临时数组bp[k++]中元素复制到A[i]做

4、准备，从第0个元素开始复制19.for(i=p;i<=r;i++)20.A[i]=bp[k++];将临时数组bp[k++]中元素复制到A[i]21.deletebp;收回缓冲区22.}