两个有序数组合并

描述

给出一个整数数组 和有序的整数数组 ，请将数组 合并到数组 中，变成一个有序的升序数组
注意：
1.可以假设 数组有足够的空间存放 数组的元素， 和 中初始的元素数目分别为 和 ，的数组空间大小为 +
2.不要返回合并的数组，返回是空的，将数组 的数据合并到里面就好了
3.数组在[0,m-1]的范围也是有序的

例1:
A: [4,5,6,0,0,0]，m=3
B: [1,2,3]，n=3
合并过后A为:
A: [1,2,3,4,5,6]

解法一：

    /**
     * 两个有序数组合并
     * 逆向解法
     *
     * @param A 数组A
     * @param B 数组B
     * @param m 数组A的元素长度
     * @param n 数组B的元素长度
     */
    private void mergeArray(int[] A, int[] B, int m, int n) {

        int A_index, B_index, A_end_index;

        A_index = m - 1;
        B_index = n - 1;
        A_end_index = m + n - 1;

        while (A_index >= 0 || B_index >= 0) {
            if (A_index >= 0 && B_index >= 0 && A[A_index] > B[B_index]) {
                A[A_end_index] = A[A_index];
                A_index--;
                A_end_index--;
            } else {
                if (B_index >= 0) {
                    A[A_end_index] = B[B_index];
                    B_index--;
                    A_end_index--;
                }
            }
            if (A_index < 0) {
                if (B_index >= 0) {
                    A[A_end_index] = B[B_index];
                    B_index--;
                    A_end_index--;
                }
            }
            if (B_index < 0) {
                if (A_index >= 0) {
                    A[A_end_index] = A[A_index];
                    A_index--;
                    A_end_index--;
                }
            }
        }
    }

解法二：

    /**
     * 两个有序数组合并
     * 正向解法
     *
     * @param A 数组A
     * @param B 数组B
     * @param m 数组A的元素长度
     * @param n 数组B的元素长度
     */
    public void mergeArray2(int[] A, int[] B, int m, int n) {
        // 分别用来记录 A和B的增量索引
        int p1 = 0, p2 = 0;

        /*
            int[] A = {4,5,6, 0, 0, 0};
            int[] B = {1,2,3};
         */
        // 新创建一个数组
        int[] tem = new int[m + n];

        while (p1 < m || p2 < n) {
            int cur;
            if (p1 == m) {
                // 当A中的元素已经遍历完了
                cur = B[p2++];
            } else if (p2 == n) {
                // 当B中的元素已经遍历完了
                cur = A[p1++];
            } else if (A[p1] < B[p2]) {
                cur = A[p1++];
            } else {
                cur = B[p2++];
            }
            tem[p1 + p2 - 1] = cur;
        }

        for (int i = (m + n - 1); i >= 0; i--) {
            A[i] = tem[i];
        }

    }