博客

**题目：**给你两个有序整数数组 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]

考察：数组，数组小应用，有序数组，归并排序的思想

思路：题目的本质是将数组nums2中的元素，插入到nums1中，并返回插入后的有序的数组nums1.

题目中要求将nums1在变成有序数组，并有提示nums1足够长>=m+n，且本题中的nums1与2都是升序数组，从小到大排序，可以理解为从数组末尾开始找，找到最大，并将其依次插入到nums1中，同时下标向前移动一位。

最后的新数组nums1，相当于长度为m+n的一个新数组。

var merge=function(nums1,m,nums2,n){
	var k=m+n-1;//新数组nums1的末尾
	var i=m-1,j=n-1; //分别定位到给定数组nums1和nums2的末尾
	while(i>=0&&j>=0){
		if(nums2[j]>=nums1[i]){
			nums1[k]=nums2[j];
			j--;
		}else{
			nums1[k]=nums1[i];
			i--;
		}
		k--;
	}
	while(j>=0){
		nums1[k]=nums2[j];
		j--;
		k--;
	}
	return nums1;
	
}

**

归并排序：

**

归并排序是用分治思想，分治模式在每一层递归上有

三个步骤

：

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果。
  
  
  实现逻辑：
  
  
  ① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  
  ② 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  
  ③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  
  ④ 重复步骤③直到某一指针到达序列尾
  
  ⑤ 将另一序列剩下的所有元素直接复制到合并序列尾

以一组无序数列｛14，12，15，13，11，16｝为例分解说明，如下图所示：



上图中首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。