数据结构与算法-归并排序

2018-03-31  本文已影响0人  星空下奔跑

将两个或两个以上有序序列组合成一个新的有序表。

void MergeSort(Sqlist &L1,Sqlist &L2,Sqlist N){
    for(i=1,j=1,k=1;i<=L1.length&&j<=L2.lenght;k++){
        if(LT(L1.r[i],L2.[j])){
            N.r[k]=L1.[i++];
        }else{
            N.r[k]=L2.[j++];
        }
    }//for
    while(i<=L1.length){N.r[k++]=L1.r[i];}
    while(j<=L2.length){N.r[k++]=L2.r[j];}
}//MergeSort
    

Java实现:


 private void mergeSort(int[] a,int[] b){

        int lenA=a.length;
        int lebB=b.length;
        quickSort(a,0,lenA-1);
        quickSort(b,0,lebB-1);
        int[] c = new int[lebB + lenA];
        int ia=0,ib=0,ic=0;
       /* while (ic<lebB+lenA) {
            if (a[ia] < b[ib]) {
                c[ic] = a[ia];
                if (ia < lenA - 1)
                    ia++;
            } else {
                c[ic] = b[ib];
                if (ib < lebB - 1)
                    ib++;
            }
            ic++;
        }*/
       //youhua
        for (; ia < lenA && ib < lebB; ) {
            if (a[ia]<b[ib]) c[ic] = a[ia++];
            else c[ic]=b[ib++];
            ic++;
        }
        if (ia<lenA)
            for (int i = ia; i < lenA; i++) {
                c[ic]=a[i];
                ic++;
            };
        if (ib < lebB ) {
            for (int i = ib; i < lebB; i++) {
                c[ic]=b[i];
                ic++;
            }
        }

        println(c);
    }
上一篇 下一篇

猜你喜欢

热点阅读