题目：
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 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]
思路：
①：丑陋的代码 时间复杂度 O(n^2)
组合以后再排序
System.arraycopy(nums2, 0, nums1, m, n);
Arrays.sort(nums1);
②美丽的代码 时间复杂度O(n+m)
双指针从前往后，最直接的算法实现是将指针p1 置为 nums1的开头， p2为 nums2的开头，在每一步将最小值放入输出数组中。由于 nums1 是用于输出的数组，需要将nums1中的前m个元素放在其他地方，也就需要 O(m) 的空间复杂度。
③更美丽的代码 时间复杂度 : O(n + m) 空间复杂度 : O(1)。
双指针 / 从后往前
双指针
代码：
//①：丑陋的代码 时间复杂度 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;
}
}
}
}
}
//②美丽的代码 时间复杂度O(n+m) 空间复杂度 : 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);
}
}
}
//更美丽的代码 时间复杂度 : O(n + m) 空间复杂度 : 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);
}
}
