88.合并两个有序数组（LeetCode ）——C语言
合并两个有序数组，根据题目的条件不一样，细节处理也不一样。我想先单纯的讨论下合并两个有序数组，不作时间及空间复杂度的限制。算法
只合并两个有序数组
这里，只合并两个有序数组，不是彻底在LeetCode88题的条件上解题，我只是想挖掘多一点的思路。在这里我只合并两个有序数组为一个有序数组，没有其余条件限制，后面将讨论LeetCode88题的解法。 高手可略过。
有两种思路，一种是先合并数组，而无论它是否有序，而后将合并以后的数组排序。另外一种思路是，在合并数组的过程当中，对元素进行排序，合并结束，排序也结束，这种思路借鉴了归并排序的归并过程，即它用到了数组有序这个条件。1、先将两个数组合并，而后再排序。数组
开辟一个新数组来存储这两个数组中的元素，须要O(m+n)的空间复杂度。将两个数组合并，此处不考虑这两个数组有序，所以合并数组时间花费为O(m+n)，而后排序数组（各类排序均可），这里考虑想要较好的时间复杂度，所以用快速排序，时间复杂度为O((m+n)lg(m+n))，综合起来，最终的时间复杂度为O((m+n)lg(m+n))，空间复杂度O(m+n)。函数
#include <stdio.h>
#include <stdlib.h>
void exchange(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void mergeArr(int *arr, int len, int *arr1, int len1, int *arr2, int len2)
{
for (int i = 0; i < len; i++)
{
if (i < len1)
{
arr[i] = arr1[i];
}
else
{
arr[i] = arr2[i - len1];
}
}
}
// 快速排序是一种原址排序，不须要分配新的数组空间
// 只须要分配常量空间来存储主元以及用于数组元素交换
// start和end为子数组下标的起始位置与终止位置
// 快速排序的分割数组步骤，这是快速排序的核心
int partition(int *arr, int start, int end)
{
// 获取主元
int key = arr[end];
// left不存在，故将i取值为start-1
int i = start - 1;
for (int j = start; j < end; j++)
{
// 若是arr[j]小于主元，则将i递增，那么左边小于主元的数组的
// 长度增长了1，同时将arr[i]与arr[j]交换。
// 由于在i递增以后，指向的是一个大于主元的值
// 而arr[j]则是一个小于主元的值，所以交换他们的值，交换完成
// 则i及i以前的元素都是小于主元的值，i+1到j之间则是大于主元的值
// j到end-1之间是不肯定大小的值，end即主元
if (arr[j] <= key)
{
i = i + 1;
exchange(arr + i, arr + j);
}
}
exchange(arr + i + 1, arr + end);
return i + 1;
}
// 快排也用到了分治的思想，即将大问题分割为性质相同的小问题，
// 小问题继续分割为更小的问题，一直到不能再分割，
// 而后将小问题的解合并起来，就得到最终的结果
// 所以，快排是先分割，而后在子数组上递归调用本身
void quickSort(int *arr, int start, int end)
{
if (start < end)
{
int mid = partition(arr, start, end);
quickSort(arr, start, mid - 1);
quickSort(arr, mid + 1, end);
}
}
void mergeArrSorted(int *arr, int len, int *arr1, int len1, int *arr2, int len2)
{
mergeArr(arr, len, arr1, len1, arr2, len2);
printf("merge Array: %d\n", len);
quickSort(arr, 0, len - 1);
}
int main (void) {
int arr1[] = {1, 9, 3, 4, 79, 27};
int arr2[] = {2, 56, 35, 7, 19};
int len1 = sizeof(arr1) / sizeof(*arr1);
int len2 = sizeof(arr2) / sizeof(*arr2);
int len = len1 + len2;
printf("length %d length\n", len);
int* arr = (int*)malloc(len * sizeof(int));
mergeArrSorted(arr, len, arr1, len1, arr2, len2);
for (int k = 0; k < len; k++)
{
printf("%d ", arr[k]);
}
printf("\n");
}
在把数组传递为函数的实参时，也要显式的传递函数长度。由于函数sizeof在编译时求值，传递给函数的实参所指向的数组长度肯定，可是函数的形参获取到的数组的长度在编译时是不肯定的，所以在函数内部使用sizeof获取数组长度会出现不肯定的值。
所以，在C语言中，传递数组的同时，也要显式传递数组的长度。
2、开辟一个新的数组arr，用来存储这两个有序数组中的元素。这里用到归并排序的merge方法，即将两个指针指向两个数组头部，而后比较指针所指的元素，将较小的元素保存到arr数组，并将其指针后移。重复上面的步骤，直到两个数组遍历彻底。这种方法，须要循环m+n次，所以时间复杂度为O(m+n)，可是由于须要开辟额外的空间来存储这两个数组的元素，所以空间复杂度为O(m+n)。
void mergeArrSorted(int* arr, int len, int *arr1, int len1, int *arr2, int len2)
{
int index1 = 0;
int index2 = 0;
for (int k = 0; k < len; k++)
{
// 若是是其余语言，能够在两个数组末尾各放一个Infiniti值，
// 这样判断比较到末尾时，恰好循环len次，下面的代码也可精简为
// if (arr1[index1] <= arr2[index2])
// {
// arr[k] = arr1[index1];
// index1++;
// }
// else
// {
// arr[k] = arr2[index2];
// index2++;
// }
// 由于这样就少了数组越界的判断
// 下面的代码的三个外层判断，就是为了防止数组访问越界
if (index1 < len1 && index1 < len2)
{
if (arr1[index1] <= arr2[index2])
{
arr[k] = arr1[index1];
index1++;
}
else
{
arr[k] = arr2[index2];
index2++;
}
}
else if (index1 < len1 && index1 >= len2)
{
arr[k] = arr1[index1];
index1++;
}
else if (index1 >= len1 && index1 >= len2)
{
arr[k] = arr2[index2];
index2++;
}
}
}
下面是测试代码：性能
#include <stdio.h>
#include <stdlib.h>
void mergeArrSorted(int* arr, int len, int *arr1, int len1, int *arr2, int len2)
{
int index1 = 0;
int index2 = 0;
for (int k = 0; k < len; k++)
{
if (index1 < len1 && index1 < len2)
{
if (arr1[index1] <= arr2[index2])
{
arr[k] = arr1[index1];
index1++;
}
else
{
arr[k] = arr2[index2];
index2++;
}
}
else if (index1 < len1 && index1 >= len2)
{
arr[k] = arr1[index1];
index1++;
}
else if (index1 >= len1 && index1 >= len2)
{
arr[k] = arr2[index2];
index2++;
}
}
}
int main (void) {
int arr1[] = {1, 3, 4, 5, 8};
int arr2[] = {2, 7, 10, 18, 21};
int len1 = sizeof(arr1) / sizeof(int);
int len2 = sizeof(arr2) / sizeof(int);
int len = len1 + len2;
int* arr = (int*)malloc(len * sizeof(int));
mergeArrSorted(arr, len, arr1, len1, arr2, len2);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
LeetCode原题：
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
条件说明：测试
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
- 你能够假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
读完题目能够知道，题目要求将子数组nums2合并到nums1，由于nums1有足够的空间可以容纳两个数组的全部元素。跟上面合并数组比起来，有空间的要求，就是咱们必须把num2合并到num1，此外区别不大。所以，上面讲过的两种方法均可以实现数组合并。
方法一：
不须要额外的空间保存数组，只需将num2保存到num1后面，而后对nums1进行快速排序便可。所以，时间复杂度不变，仍是O((m+n)lg(m+n))，即快排的时间复杂度。空间复杂度为O(1)，由于不须要开辟额外的空间。
方法二：
由于须要将nums1做为输出数组，所以，要先将nums1的元素存储到一个新的数组，而后使用双指针法，比较两个数组中的元素大小，并依次将其保存到nums1。所以须要额外开辟m的空间来存储nums1中的元素。所以空间复杂度O(m)，时间复杂度不变，为O(m+n)。
方法三：
能够看到，第一种方法空间复杂度很优秀，可是时间复杂度逊色于第二种方法。咱们须要找出时间复杂度如方法二通常优秀，空间复杂度如方法一通常优秀的算法，那就是双指针法--从后往前遍历。
双指针从后往前遍历，将较大的值存储到nums1尾部，如此循环，直到全部元素都有序存储到nums1中。时间复杂度O(m+n)，空间复杂度O(1)。ui
void merge(int *nums1, int nums1Size, int m, int *nums2, int nums2Size, int n)
{
int len = m + n;
m = m - 1;
n = n - 1;
for (int i = len - 1; i >= 0; i--)
{
if (n >= 0 && m >= 0)
{
if (nums2[n] > nums1[m])
{
nums1[i] = nums2[n];
n--;
}
else
{
nums1[i] = nums1[m];
m--;
}
}
else if (n >= 0 && m < 0)
{
nums1[i] = nums2[n];
n--;
}
else if (n < 0 && m >= 0)
{
nums1[i] = nums1[m];
m--;
}
}
}
下面是测试代码，有兴趣的能够拿去编译运行一下：spa
#include <stdio.h>
#include <stdlib.h>
void merge(int *nums1, int nums1Size, int m, int *nums2, int nums2Size, int n)
{
int len = m + n;
m = m - 1;
n = n - 1;
for (int i = len - 1; i >= 0; i--)
{
if (n >= 0 && m >= 0)
{
if (nums2[n] > nums1[m])
{
nums1[i] = nums2[n];
n--;
}
else
{
nums1[i] = nums1[m];
m--;
}
}
else if (n >= 0 && m < 0)
{
nums1[i] = nums2[n];
n--;
}
else if (n < 0 && m >= 0)
{
nums1[i] = nums1[m];
m--;
}
}
}
int main (void) {
int arr1[10] = {1, 2, 3, 8, 20};
int arr2[] = {6, 9, 10};
int len1 = sizeof(arr1) / sizeof(*arr1);
int len2 = sizeof(arr2) / sizeof(*arr2);
int m = 5;
int n = len2;
int len = m + n;
merge(arr1, len1, m, arr2, len2, n);
for (int i = 0; i < len; i++)
{
printf("%d ", arr1[i]);
}
printf("\n");
}