資料結構與算法分析筆記與總結(java實作)--排序9：有序數組合并練習題

題目：有兩個從小到大排序以後的數組A和B，其中A的末端有足夠的緩沖空容納B。請編寫一個方法，将B合并入A并排序。給定兩個有序int數組A和B，A中的緩沖空用0填充，同時給定A和B的真實大小int n和int m，請傳回合并後的數組。

思路：已知兩個數組都是有序的，最終需要将B數組合并到A數組中來，注意了解，數組不同于集合，沒有容量這個概念，隻有長度，即數組中的長度必須是明确的，且裡面必須填充資料，不能僅僅占用、保留白間而不存放資料，是以題目中采取的方式是在A數組的後面緩沖空間填充0，而int  n，int m指的是數組的真實長度，即非0元素的數目，此時A.length與n；B.length與m是不相等的n，m隻是A，B的前面一個部分而已。本題的解決政策很簡單，對于兩個數組的真實值部分，即使用2個指針從i=n-1和i=m-1開始從後向前周遊數組A，B，比較得到較大的值将其放到i=m+n-1的位置；一直向前周遊數組A，B，直到如果B數組周遊完成，那麼就已經合并完成了，直接傳回A即可；如果A數組先周遊完成，那麼不需要比較了，直接将B數組中的剩餘元素放入到A數組中即可。

importjava.util.*;

//已知數組A,B有序将其合并；注意着了A.length不等于n

publicclass Merge {

    public int[] mergeAB(int[] A, int[] B, intn, int m) {

       //特殊輸入

        if(B==null||B.length<=0) return A;

        //從後向前周遊數組A,B，将較大值放入到數組A中

        int p1=n-1;

        int p2=m-1;

       //較大值從A數組的m+n-1的位置開始向前存放

        int p=m+n-1;

        while(p2>=0&&p1>=0){

        //此時數組B沒有周遊完成，将較大值放入到數組A的末尾

           A[p--]=(A[p1]>B[p2]?A[p1--]:B[p2--]);

        }

        //如果B數組周遊完成，那麼A中的剩餘元素不用動了，直接傳回即可

        if(p2<0) return A;

       //如果A數組周遊完成，那麼将B中的元素不用比較直接複制到A數組中即可

        if(p1<0){

            while(p2>=0){

                A[p--]=B[p2--];

            }

        }

       //此時A，B數組都完成合并，記得傳回結果

        return A;

    }

}