力扣面试经典150 88. 合并两个有序数组 归并排序的merge函数

题目链接

规定了时间我首先想到的是归并排序，以时间换空间，题目要求时间复杂度O(m+n)
提示：

nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[j] <= 109

而且这个题理论上，是合并，所以得把最后合并的结果放到nums1[]上
下面是代码

classSolution{public:voidmerge(vector<int>&nums1,intm,vector<int>&nums2,intn){vector<int>temp(nums1.begin(),nums1.begin()+m);intp=0;intp1=0;intp2=0;while(p1<m&&p2<n){if(temp[p1]<=nums2[p2])nums1[p++]=temp[p1++];elsenums1[p++]=nums2[p2++];}while(p1<m)nums1[p++]=temp[p1++];while(p2<n)nums1[p++]=nums2[p2++];}};

然后再复习一下归并排序
这么多年了，发现自己学习算法过于死板
其实归并排序是一棵归并排序二叉树。

那么一涉及到树就很容易理解，这里头有递归，所以归并排序是由递归和merge函数组合来实现的，那个大的递归函数就是

voidmergeSort(vector<int>&arr,intl,intr){if(l>=r)return；intmid=(l+r)/2;mergesort(arr,l,mid);mergesort(arr,mid,r);merge(arr,l,mid,r);}

下面是完整的归并排序的代码

#include<iostream>#include<vector>using namespace std;// 合并两个有序区间 [l, mid] 和 [mid+1, r]voidmerge(vector<int>&arr,intl,intmid,intr){vector<int>temp(r-l+1);inti=l;intj=mid+1;intk=0;while(i<=mid&&j<=r){if(arr[i]<=arr[j]){temp[k++]=arr[i++];}else{temp[k++]=arr[j++];}}while(i<=mid)temp[k++]=arr[i++];while(j<=r)temp[k++]=arr[j++];// 复制回原数组for(intp=0;p<temp.size();++p){arr[l+p]=temp[p];}}// 归并排序递归voidmergeSort(vector<int>&arr,intl,intr){if(l>=r)return;intmid=(l+r)/2;mergeSort(arr,l,mid);mergeSort(arr,mid+1,r);merge(arr,l,mid,r);}intmain(){vector<int>arr={5,2,9,1,5,6,3,8};cout<<"排序前：";for(intx:arr)cout<<x<<" ";cout<<endl;mergeSort(arr,0,arr.size()-1);cout<<"排序后：";for(intx:arr)cout<<x<<" ";cout<<endl;return0;}

直接从后面替换插入的方法

classSolution{public:voidmerge(vector<int>&nums1,intm,vector<int>&nums2,intn){inti=nums1.size()-1;n--;m--;while(n>=0){while(m>=0&&nums1[m]>nums2[n]){swap(nums1[i--],nums1[m--]);}swap(nums1[i--],nums2[n--]);}}};