子函數(shù)merge()

《子函數(shù)merge()》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、合并排序中用到的子函數(shù)merge()，功能是合并兩個有序的子數(shù)組，其算法如下：輸入：整數(shù)數(shù)組A[]，下標(biāo)p,q,r,元素個數(shù)m。A[p]~A[q]及A[q+1]~A[r]已按遞增順序排序輸出：按遞增順序排序的子數(shù)組A[p]~A[r]題意：合并兩個遞增子數(shù)組A[p]~A[q]及A[q+1]~A[r]，合并后按遞增順序排序。1.voidmerge(intA[],intp,intq,intr,intm)2.{3.int*bp=newint[m]；分配緩沖區(qū)，存放被排序的元素4.inti,j,k;5.i=p;j=q+1;k=0;i表示子數(shù)組A[p]~A[q]中當(dāng)前元

2、素所在的位置；j表示子數(shù)組A[q+1]~A[r]中當(dāng)前元素所在的位置6.while(i<=q&&j<=r)表示子數(shù)組A[p]~A[q]中當(dāng)前元素所在的位置以及子數(shù)組A[q+1]~A[r]中當(dāng)前元素所在的位置都沒有超過各自的子數(shù)組范圍7.if(A[i]<=A[j])比較子數(shù)組A[p]~A[q]和子數(shù)組A[q+1]~A[r]中當(dāng)前元素的大小8.bp[k++]=A[i++]將較小的元素先裝入臨時數(shù)組bp[]；然后使元素的序列自增，于是下一輪循環(huán)就可以比較下一組元素的大小了9.else10.bp[k++]=A[j++];較大的元素后裝入臨時數(shù)組bp[]11.}12.

3、if(i==q+1)如果子數(shù)組A[p]~A[q]中的元素已經(jīng)全部裝入臨時數(shù)組bp[]（先裝入的是較小的元素）13.{for(;j<=r;j++)14.bp[k++]=A[j];}那么就將子數(shù)組A[q+1]~A[r]中剩下的元素全部裝入臨時數(shù)組bp[]15.else否則一就定是子數(shù)組A[q+1]~A[r]中的元素已經(jīng)全部裝入臨時數(shù)組bp[]（先裝入的是較小的元素）16.{for(;i<=q;i++)17.bp[k++]=A[i];}于是，將子數(shù)組A[p]~A[q]中剩下的元素全部裝入臨時數(shù)組bp[]18.k=0;為將臨時數(shù)組bp[k++]中元素復(fù)制到A[i]做

4、準(zhǔn)備，從第0個元素開始復(fù)制19.for(i=p;i<=r;i++)20.A[i]=bp[k++];將臨時數(shù)組bp[k++]中元素復(fù)制到A[i]21.deletebp;收回緩沖區(qū)22.}