題目：

給定兩個有序整數(shù)數(shù)組 nums1 和 nums2键兜，將 nums2 合并到 nums1 中苇经，使得 num1 成為一個有序數(shù)組叹谁。

說明:

初始化 nums1 和 nums2 的元素數(shù)量分別為 m 和 n藏否。
你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素门驾。

示例：

示例:

輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

輸出: [1,2,2,3,5,6]

思路：

①：丑陋的代碼 時間復(fù)雜度 O(n^2)
組合以后再排序

System.arraycopy(nums2, 0, nums1, m, n);
Arrays.sort(nums1);

②美麗的代碼 時間復(fù)雜度O(n+m)
雙指針從前往后，最直接的算法實現(xiàn)是將指針p1 置為 nums1的開頭娃善， p2為 nums2的開頭论衍，在每一步將最小值放入輸出數(shù)組中。由于 nums1 是用于輸出的數(shù)組聚磺，需要將nums1中的前m個元素放在其他地方坯台，也就需要 O(m) 的空間復(fù)雜度。

③更美麗的代碼 時間復(fù)雜度 : O(n + m) 空間復(fù)雜度 : O(1)瘫寝。
雙指針 / 從后往前

雙指針

代碼：

//①：丑陋的代碼 時間復(fù)雜度 O(n^2)
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        int temp = 0;
        int index = m; //index = m = 3
        for (int i : nums2) {
            nums1[index] = i;//nums[3] = 2
            index++;//index = 4
        }//nums1 = 1,2,3,2,5,6
        
        for (int j = 0; j < nums1.length - 1; j++){
            for (int i = 0; i < nums1.length - 1 - j; i++) {
                if (nums1[i+1] < nums1[i]) {
                    temp = nums1[i];
                    nums1[i] = nums1[i+1];
                    nums1[i+1] = temp;
                }
            }
        }
        
    }
}

//②美麗的代碼 時間復(fù)雜度O(n+m) 空間復(fù)雜度 : O(m)
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int newNums[] = new int[m];
        System.arraycopy(nums1, 0, newNums, 0, m);
        int p = 0;
        int p1 = 0;
        int p2 = 0;
        while (p1 < m && p2 < n) {
            if (newNums[p1] > nums2[p2]) {
                nums1[p] = nums2[p2];
                p2++;
            } else {
                nums1[p] = newNums[p1];
                p1++;
            }
            p++;
        }
        if (p1 < m) {
            System.arraycopy(newNums, p1, nums1, p, m-p1);
        }
        if (p2 < n) {
            System.arraycopy(nums2, p2, nums1, p, n-p2);
        }
        

    }
}

//更美麗的代碼 時間復(fù)雜度 : O(n + m) 空間復(fù)雜度 : O(1)蜒蕾。
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        int p = m + n - 1;
        int p1 = m - 1;
        int p2 = n - 1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums2[p2] > nums1[p1]) {
                nums1[p] = nums2[p2];
                p2--;
            }else {
                nums1[p] = nums1[p1];
                p1--;
            }
            p--;
        }
        System.arraycopy(nums2, 0, nums1, 0, p2+1);
        
        
    }
}