非递减顺序，就是前一个元素小于等于后一个元素
想法一
直接把两个数组合并，进行qosrt（快排）
不过排序消耗过大，时间复杂度太高，pass！
想法二
正常情况下，合并两个有序数组，我们是创建一个新的数组，从头开始比较两个数组的元素，取小的尾插新数组
分析上图：开头1和2比较，1小，尾插数组；然后2和2比较，一样，选哪一个都行……依此类推
想法三
但是这里的这道题是想法二的变式，它要求将所有数据放入数组nums1中，不能创建新数组，那应该怎么办呢？
其实，转换一下思路就可以，我们从尾比较，取大的尾插即可
这里还要讨论一下，end1和end2谁先小于0， 如果是end2先小于0，那就代表所有数据已经排序并放在nums1中；但如果是end1先小于0，那nums2中还有数据没放进nums1中，此时单独循环，将nums2的数据放入其中
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int end1 = m-1; int end2 = n-1; int i = m+n-1; while (end1 >=0 && end2 >=0) { if (nums1[end1] < nums2[end2]) { nums1[i--] = nums2[end2--]; } else { nums1[i--] = nums1[end1--]; } } while(end2 >= 0) { nums1[i--] = nums2[end2--]; } }
这道题表面考顺序表（数组），其实是归并排序的缩影
