给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
题解1
直接将两个数组相加，采用java.util下的 Arrays.sort() 方法重新排序，简单有效。
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i < n; i++) {
nums1[m + i] = nums2[i];
}
Arrays.sort(nums1);
}
Arrays.sort小数组底层-插入排序
采用数组nums={1，4，7，2，5，6}作为例子
1.将数组传入快速排序中排序；
2.数组长度减1小于286的进入这个排序方法；
3.很明显数组长度小于47的时候则优先使用插入排序
4.按左边进行插入排序：
① 当数组中的两个元素进行比较大小时，先取出右边的元素存入ai中，
② 将右边的元素与左边的元素进行比较；
Ⅰ、如果右边的元素大于等于左边的元素，则插入原位置；
Ⅱ、若果右边的元素小于左边的元素，会将左边所有大于右边的元素后移一位，循环一次则指针索引 j--，代表右边的元素前移一位，最终覆盖原有元素。
时间复杂度为O( (m+n)log(m+n) )。
题解2
采用双指针和临时数组的方法对两数组排序；
- 同时遍历两个数组，如果nums1中取出的元素小于nums2中取出的元素，则将nums1中的元素放入临时数组；
- 如果nums1中取出的元素大于等于nums2中取出的元素，则将nums2中的元素放入临时数组；
- 将临时数组中的元素放入nums1中；
时间复杂度O（m+n），空间复杂度O(m+n);
public void merge(int[] nums1, int m, int[] nums2, int n) {
//建立临时数组
int k = m + n;
int[] temp = new int[k];
//循环数组，建立双指针比较
for (int i = 0, nums1Index = 0, nums2Index = 0; i < k; i++) {
//数组1中指针超过索引长度，代表数组1的元素已取完则将数组2中元素放入临时数组
if (nums1Index >= m) {
temp[i] = nums2[nums2Index++];
} else if (nums2Index >= n) {
//数组2中指针超过索引长度，则将数组1中的元素放入临时数组
temp[i] = nums1[nums1Index++];
} else if (nums1[nums1Index] < nums2[nums2Index]) {
//如果数组1中指针指的元素小于数组2中指针指的元素，将数组1中的元素放入临时数组
temp[i] = nums1[nums1Index++];
} else {
//数组1中指针指的元素大于等于数组2中指针指的元素，将数组2的元素放入临时数组
temp[i] = nums2[nums2Index++];
}
}
//将临时数组放入数组1中
for (int i = 0; i < temp.length; i++) {
nums1[i] = temp[i];
}
题解2优化
- 题解2中是创造了一个临时数组，其实数组nums1中的长度为m+n可以将两个数组同时放入的；
- 采用双指针和一个数组的方法；
- 取出两个数组指向的元素，元素大的倒序放入nums1数组中。
时间复杂度O（m+n），空间复杂度O(1);
public void merge3(int[] nums1, int m, int[] nums2, int n) {
//nums1有效元素为m个，但nums1的初始长度为m+n，我们可以将两个数组比较大的元素放入数组1中后面的位置
for (int i = m + n - 1, nums1Index = m - 1, nums2Index = n - 1; i >= 0; i--) {
if (nums1Index < 0) {
//如果nums1中的指针小于0，则代表nums1中元素已经没有了，将nums2中的元素放入nums1中的指定位置
nums1[i] = nums2[nums2Index--];
} else if (nums2Index < 0) {
//如果nums2中的指针小于0，直接退出即可，
break;
} else if (nums1[nums1Index] <= nums2[nums2Index]) {
//如果nums2中的元素大于等于nums1中的元素，将nums2中的元素放入数组对应位置
nums1[i] = nums2[nums2Index--];
} else {
//如果nums2中的元素小于nums1中元素，将nums1中的元素取出放入对应位置
nums1[i] = nums1[nums1Index--];
}
}
}