合并两个有序数组讲解

 原题出处： . - 力扣（LeetCode）

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {

}

 将两个非递减顺序的数组进行合并，但是最后的数组仍然要非递减，也就是递增。

方法一：直接合并再使用qsort函数进行排序

因为这道题的nums1数组的大小是包含nums1Size和nums2Size的，只需要将nums链接在数组nums1的有效数据的后面即可。

	for (int i = 0; i < n; i++) {
		nums1[i + m] = nums2[i];
	}

此时的nums1数组的顺序并不是递增的，然后我们再使用qsort 进行排列，因为qsort函数的底层是快速排列，速度更快，这道题并没有时间复杂度的限制，当然也可以使用冒泡排序。

这里不过多讲解qsort函数的使用，有问题可以私信。

最后完成qsort的第三个参数函数就可以了

int cmp(const void* p1, const void* p2) {
	return *(int*)p1 - *(int*)p2;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
	for (int i = 0; i < n; i++) {
		nums1[i + m] = nums2[i];
	}
	qsort(nums1,m + n,sizeof(nums1[0]),cmp);
}

方法2：双指针

使用双指针的话，这里我们可以再创建一个数组 ，使用两个指针分别指向两个数组的头部，然后比较谁更小，将小的拿到新的数组中，指针加1，直到完成遍历。

但是这样的方法还可以优化，如何在不使用新数组的情况下，完成这道题呢。

我们使用新数组的原因是当我们直接在nums1中移动数据的时候，可能会覆盖数据。

可是如果我们使用逆向双指针，就不会了，因为在nums1中后面的数据都是0，这些不是有效的数据，我们不用考虑数据被覆盖的问题。

	int end1 = m - 1;//指向第一个数组的有效数据最后一个
	int end2 = n - 1;//指向第二个数组的有效数据最后一个
	int newend = nums1Size - 1;//指向新的数组
	while (end1 >= 0 && end2 >= 0) {
		if (nums1[end1] > nums2[end2]) {
			nums1[newend] =  nums1[end1];
			newend--;
			end1--;
		}
		else {
			nums1[newend] = nums2[end2];
			end2--;
			newend--;
		}
	}

为了防止越界访问，while循环的条件是两个end都要大于等于0。这样写有问题吗？

有问题

在最后跳出循环的时候，有两种情况，第一种是

end2小于0了，此时数组2中的数据全部都在nums1中了，此时是没有问题的。

第二种情况是end1先为负，此时nums2中的数据并没有移动完，如果我们直接返回此时就是错误的了。所以我们在最后应该再判断一下。

 	while (end2 >= 0) {
		nums1[end2] = nums2[end2];
		end2--;
	}

如果end1先为负，我们再把数组2中剩余的数据移到数组1中即可。

最后考虑一个问题，如果数组1中没有有效数据怎么办？

nums2就是我们要得到的数组，这个代码是可以解决这个问题，因为我们最后把数组2的数据移动到了数组1中。

同理如果数组2没有数据呢？

我们可以在开头加一个判断，如果n为0直接结束函数。

if(n == 0)
    return;

这样就不用后续了，但是不加也可以。