Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

问题需求：

1，给定两个有序数组，合并成为一个数组，结果数组仍然有序。

2，nums1的长度等于或者大于两个数组长度总和，不用担心nums1的长度不够用的问题。

解题思路：一共想到两类解法，分别牺牲时间或者空间，细说如下。

解法一：

1，先将两个数组直接合并，就是直接将nums2数组里的所有元素，都拷贝到nums1数组的剩余空间里面。

2，任意选择一类排序方法，对nums1数组进行排序（本例所用的方法是选择排序）。

3，时间复杂度：取决于你选择的排序方式了，空间复杂度=O(1)。

解法二：

1，重新申请一段长度=m+n的空间，将两数组里的元素按照顺序拷贝到新的空间里。

2，将新空间里的元素重新拷贝到原来的nums数组里面。

3，时间复杂度=O(n)，因为只要遍历两次整个数组就可以了，空间复杂度=O(n)。

void merge(int* nums1, int m, int* nums2, int n) {
    /*
    1,先将两个数组直接拷贝到一起去。
    2,对新数组进行排序，任选一个排序方式即可
    */
    int p = 0,q = 0,min = 0,temp = 0;//定义两个工作指针
    if(n==0) return;//边界
    if(m==0){//边界
        for(int i = 0;i<n;i++){
            nums1[i] = nums2[i];
        }    
        return;
    }
    //先将数组元素拷贝到一起去
    //然后进行一轮排序
    p = m;
    //拷贝
    while(q<n){
        nums1[p] = nums2[q];
        p++;
        q++;
    }
    //排序
    for(p = 0;p<n+m;p++){
        min = p;
        for(q = p;q<n+m;q++){
            if(nums1[q]<nums1[min]) min = q;
        }
        if(min!=p){
            temp = nums1[min];
            nums1[min] = nums1[p];
            nums1[p] = temp;
        }
    }
    
}

void merge(int* nums1, int m, int* nums2, int n) {
    int p = 0,q = 0,num = 0,temp = 0;
    int* nums = NULL;
    if(n==0) return;//边界
    if(m==0){//边界
        for(int i = 0;i<n;i++){
            nums1[i] = nums2[i];
        }    
        return;
    }
    nums = (int*)malloc((n+m)*sizeof(int));//申请新的内存空间作为缓存
    //将两数组按照顺序拷贝到新空间里面
    while(p<m&&q<n){
        if(nums1[p]<=nums2[q]){
            nums[num] = nums1[p];
            p++;
        }else{
            nums[num] = nums2[q];
            q++;
        }
        num++;
    }
    //将其中的一个数组剩余元素都拷过去
    if(p==m){
        while(num<n+m){
            nums[num] = nums2[q];
            num++;
            q++;
        }
    }else{
        while(num<n+m){
            nums[num] = nums1[p];
            num++;
            p++;
        }
    }
    //将缓存区所有元素考到原来数组里面
    p = 0;
    while(p<n+m){
        nums1[p] = nums[p];
        p++;
    }
}