004、合并两个有序数组

0、题目描述

合并两个有序数组

1、法1

数组nums1有m个元素， 直接在下标为m的位置处追加nums2的元素。然后再qsort整体排序。
——

——
qsort函数，（数组首元素地址，排序的个数，排序元素大小， 比较函数）
注意比较函数里面的参数要传递指针

int Cmp(int* a, int* b)
{
    return *a - *b;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
   int p1 = m;
   int p2 = 0;
	
	//n为0，说明不插入元素，nums1里面也没多余的位置，直接返回就可以了
   if (n == 0)
   {
        return;
   }

   while (n)
   {
        nums1[p1++] = nums2[p2++];
        n--;
   }

    qsort(nums1, nums1Size, sizeof(int), Cmp);    
}

2、法2

创建一个新数组sorted来存储数据，再去把排好序的数组粘到nums1里。创建3个指针在三个数组里移动，把较小的数据先放进去。注意：

• 当第一个数组nums1走完的时候，后面的数据有可能是0，这时候比较两数组时0是较小的。
• nums2数组有可能发生越界访问。
  
  在运行判例4的时候就有问题了。nums1[2] = [ 2 , 0 ] ， nums2[1] = [ 1 ]
  这个判例走读代码发现，第一次循环把nums2里面唯一的元素拿出来放到sorted里面的之后，p2++。
  这时候再去访问nums2就已经越界了。所以这个条件还是应该拿两个数组下标来分情况讨论。还得多分支。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    int len = m + n;
    int p1 = 0;
    int p2 = 0;
    int ps = 0;
    int sorted[m + n];

    if (n == 0)
    {
        return;
    }
	// 有len个元素需要被排序，所以一定循环len次
    while (len--) 
    {	
    //当两个数组下标都越界的时候，循环还没结束，就把另个数组的元素放到sorted数组里
        if (p1 == m)
        {
            sorted[ps++] = nums2[p2++];
        }
        else if (p2 == n)
        {
            sorted[ps++] = nums1[p1++];
        }
        else if (nums1[p1] < nums2[p2])
        {
            sorted[ps++] = nums1[p1++];
        }
        else
        {
            sorted[ps++] = nums2[p2++];
        }
    }
	//把sorted数组里的元素再粘贴到nums1里
    for (int i = 0; i < m + n; i++)
    {
        nums1[i] = sorted[i];
    }

}

3、法3

和第二种方法类似，只不过是倒着比较大小，这样的好处是，0一定小于有效元素，而且不需要创建新数组直接在nums1里面操作不会损失数据。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    int p1 = m - 1;		//数组1最后一个有效元素的下标
    int p2 = n - 1;		//数组2最后一个有效元素的下标
    int p = m + n - 1;	//数组1最后一个元素的下标

	//这个条件保证两数组不会越界，但有可能数组1里面没有有效元素了，而数组2里面还有
    while (p1 >= 0 && p2 >= 0)
    {
        if (nums1[p1] > nums2[p2])
        {
            nums1[p--] = nums1[p1--];
        }
        else
        {
            nums1[p--] = nums2[p2--];
        }
    }
	//把数组2里面的元素依次放进去
    while (p2 >= 0)
    {
        nums1[p--] = nums2[p2--];
    }
}