今天的题目是 合并两个有序数组，我们先来看下题目要求：
 
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 
合并到 nums1 中，使 nums1 成为一个有序数组。
说明：

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
 
示例：

输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出：[1,2,2,3,5,6]

 
看到这个题目第一眼，你是不是也和我一样想到了直接把两个数组放在同一个数组里边，然后调用Arrays.sort() 然后就直接得到了结果呢，这样是可以的 但是浪费了题目中的 原数组也是有序的这个条件，且这样做的复杂度很高，为什么呢？
 
nums2数组拷贝到nums1数组，因为数组在物理内存中是连续的存储单元，合并数组时，
本身并不会耗费很多的时间和空间，但是sort方法的底层是一种快速排序的方法，时间复杂度是O(nlog n)

 
因为两个数组本身就是有序的了，我们可以利用这个条件，在原数组遍历一遍的时候直接排序就好了，所以 双指针，他来了！
 
public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n - 1 ; //两个数组合在一起 最后那个数的下标
        int i = m - 1 ; // nums1 的最后一个数的下标
        int j = n - 1 ;// nums2 的最后一个数的下标
        while(i>=0 && j>=0) {  //从后往前遍历 直到最前边的数字都遍历完
            if(nums1[i] < nums2[j]){    //当nums1的最后一个数字小于nums2的最后一个数字
            nums1[k--] = nums2[j--] ;//这说明nums2最后一个数字是合并之后数组中值最大的后头的位置
            }else{  //否则放在远处不动 继续向下遍历
                nums1[k--] = nums1[i--] ;
            }
        }
        while(j>=0) nums1[k--]= nums2[j--] ;  //当nums1已经排序完之后 但是nums2还有数据
    }
 
写完之后，我们来测试一下；
 

 搞定！
 2020年11月22日00:02:47

 
合并两个有序数组
 
1.题目： （合并两个有序数组）
2. 示例
3.解答步骤
4. 提交结果（提交用时和内存消耗）

 
 
 
声明： 题目均来自力扣，网址力扣官网， 如有侵权，告知必删！
 本题地址： 点击我跳转本题地址
 
 
1.题目： （合并两个有序数组）
 
 
 
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
 
 
2. 示例
 
 
3.解答步骤
 
 
 
思路都在注释上！ 请大家自主阅读程序！
 
 
⭐ 本篇注意点： 本题主要思想
 
 
 
答： 因为要将两个⭐有序数组，归并且保持有序。则需要对比两个数组的元素值，较小的一个放到临时数组，并且移动下标，依次对比，完成归并有序数组。
 
 
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 创建一个用于存放合并排序后的数组
        int[] tempArray = new int[m + n];
        // 创建一个用于遍历i,j的下标
        int i,j;
        i=j=0;
        // 创建一个temp数组的下标
        int tempIndex=0;

        // 进行一个while循环
        // 依次从两个数组的初始位置开始比较
        // 将较小的一方放到临时数组
        while(i<m && j<n) {
            if(nums1[i] < nums2[j]) {
                tempArray[tempIndex++] = nums1[i++];
            } else {
                tempArray[tempIndex++] = nums2[j++];
            }
        }

        // 假如有一个数组遍历完
        // 而另一个数组并不空时
        // 应当将这个数组的值全部放进tempArray
        for( ; i<m;) {
            tempArray[tempIndex++] = nums1[i++];
        }
        for(; j<n; ) {
            tempArray[tempIndex++] = nums2[j++];
        }

        // 将合并归并好的数组赋值给nums1
        for(int k=0; k<m+n; k++) {
            nums1[k] = tempArray[k];
        }
    }
}
 
4. 提交结果（提交用时和内存消耗）
 

让我们来看一下这道题的描述。
 
【题目描述】
 
 
 
题目：给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 
 
 
 
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
 
 
 
 
示例 1：
 输入：nums1 = [1,2,3,0,0,0], m = 3,
 nums2 = [2,5,6], n = 3
 输出：[1,2,2,3,5,6]
 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] 。
 
 
 
 
示例 2：
 输入：nums1 = [1], m = 1,
 nums2 = [], n = 0
 输出：[1]
 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。
 
 
 
 
示例 3：
 输入：nums1 = [0], m = 0,
 nums2 = [1], n = 1
 输出：[1]
 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。
 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
 
 
题目来源（力扣）：合并两个有序数组
 
【题目分析】
 
如果不考虑时间复杂度，那么最直接最暴力的方法是先将 nums2 数组拷到 nums1 数组的后面，然后再用一个简单的排序算法，就能解决问题了。但是在时间复杂度上几乎没有优势。
 
 
 
其实，当我们仔细再想一想，为什么给的两个数组都是有序的？直接给你两个无序数组用上面的方法不也可以解决问题吗？
 因此，如果想减小时间复杂度的话，就要特别关注给的“有序数组”这个条件，在这基础上想出另一种更优的解法。
 
 
【基本思路】
 我们想啊，两个数组不是都有序吗？那就先 malloc 一个用指针 tmp 指向的数组作辅助，每次只需把两个数组（都从前往后比较）当中较小的那个元素（被比较的那两个元素相等也可以，谁拷在前面谁拷在后面无所谓）拷进 tmp 数组（把这步做成一个循环），这样就可以保证 tmp 数组总是有序的。
 
给几个例子感受一下，（这里的 nums1 数组先不列出后面的 0 ）
 用例1：nums1 = [1,4,6,8]，nums2 = [2,3,7,9]
 用例2：nums1 = [9,11,14,15]，nums2 = [2,4,5,8]
 用例3：nums1 = [2,4,7,9]，nums2 = [3,5]
 
注意一个细节，最后必定有一个数组的元素全拷进 tmp 数组了，另一个数组至少还剩下一个元素没拷进 tmp 数组。
 因此，只需把那个数组还没拷的元素拷过去就行了。
 
题目要求将合并后的数组存储在 nums1 数组中，所以再将 tmp 数组全拷过去 nums1 数组中就行了。
 
【重要细节】
 
 
 
但是还没完！我们还要释放掉 malloc 出来的由指针 tmp 指向的数组，避免内存泄露（虽然在OJ上可以通过，不一定报错，但是我们还是要保持这个习惯，因为内存泄露的后果还是比较严重的）
 
 
最后把指针 tmp 置空。
 
 
【代码实现】
 
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int* tmp=(int*)malloc(sizeof(int)*(m+n));

    int i1 = 0,i2 = 0;
	int i = 0;
	
	//必定有一个数组中的元素全都拷进 tmp 数组了
	while (i1 < m && i2 < n)
	{
		if (nums1[i1] > nums2[i2])
			tmp[i++] = nums2[i2++];
			
		else
			tmp[i++] = nums1[i1++];
	}
	
	//无须关心还有元素没被拷贝的那个数组究竟是 nums1 还是 nums2 ，因为下面的循环必定只进入其中一个
	while (i2 < n)
	{
        tmp[i++] = nums2[i2++];
	}
	
	while (i1 < m)
	{
		tmp[i++] = nums1[i1++];
	}
	
    memcpy(nums1,tmp,sizeof(int)*(m+n)); 
    free(tmp);
    tmp=NULL;
}
 
 
 
这种解法就很优了，时间复杂度是 O(m+n) 。
 
 
更多文章
 阶乘后的零（C语言）
 调整数组顺序使奇数位于偶数前面（C语言）

合并两个有序数组为新的有序数组
 
描述：
 合并两个升序排序的整型数组为一个新的升序整型数组并输出。
 
输入格式:
 首先输入第一个数组的数据个数后输入第一个数组按升序排序的数据，然后再输入第二个数组的数据个数，最后输入第二个数据按升序排序的数据。数据之间用一个或多个空格或回车符分隔。
 
输出格式:
 输出合并后按升序排序的数组的元素，元素之间用一个空格分隔。（注意输出的最后一个元素后会有一个空格符）
 
输入样例:
 
4
 1 2 8 10
 5
 -1 5 6 20 200
 输出样例:
 
-1 1 2 5 6 8 10 20 200
 

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        //数组a
        int a=in.nextInt();
        int[] m=new int[a];
        for(int i=0;i<a;i++)
        {
            m[i]=in.nextInt();
        }
        //数组b
        int b=in.nextInt();
        int[] n=new int[b];
        for(int i=0;i<b;i++)
        {
            n[i]=in.nextInt();
        }
        //合并a,b数组
        int[] all=new int[a+b];
        for(int i=0;i<a;i++)
        {
            all[i]=m[i];
        }
        for(int i=a;i<(a+b);i++)
        {
            all[i]=n[i-a];
        }
        //冒泡排序
        int pos=0;
        for(int i=0;i<(a+b-1);i++)
        {
            for(int j=0;j<(a+b-i-1);j++)
            {

                if(all[j]>all[j+1])
                {
                    pos=all[j+1];
                    all[j+1]=all[j];
                    all[j]=pos;
                }
            }
        }
        for(int i=0;i<(a+b);i++)
            System.out.print(all[i]+" ");
    }

}