原地合并两个排序数组 O（1）空间复杂度，O(n)时间复杂度

问题：

给你两个从小到大的数组a，b。在不申请额外空间下，往a填充a和b合并后的排序数组（假设a的空间是足够的）。

第一种方法：

很直觉的思路是，我们采取和归并排序时同样的策略，每次拿出最小的元素放进去即可。但是由于每次渴望拿最小，每填充一个元素后，需要重新维护有个冒泡的过程。

第二种方法：

每次拿a,b最大的元素，好处是省略了维护冒泡的过程，复杂度降低了。

#include <bits/stdc++.h>
using namespace std;
//复杂度O(m*n)
//需要一个冒泡过程
//每次取出a,b最小值
vector<int> alg1(vector<int> a,vector<int> b){
    int as = a.size();
    a.insert(a.end(),b.begin(),b.end());
    int poi = 0;
    while(poi<as){
        if(a[poi]<a[as])poi++;
        else{
            swap(a[poi],a[as]);
            for(int i = as;i<(int)a.size()-1;i++)if(a[i]>a[i+1])swap(a[i],a[i+1]);
        }
    }
    return a;
}
//复杂度O(n)
//每次取出a,b最大值
vector<int> alg2(vector<int> a,vector<int> b){
    int i = a.size()-1;
    int j = b.size() - 1;
    a.insert(a.end(),b.begin(),b.end());
    int k = a.size()-1;
    while(i>=0 && j>=0){
        if(a[i]>b[j])a[k--] = a[i--];
        else a[k--] = b[j--];
    }
    while(j>=0)a[k--]=b[j--];
    return a;
}
int main() {
    // interesting
    vector<int> a = {5,6,7,8};
    vector<int> b = {2,3,9,11,13,45};
    
    vector<int> ret =  alg1(a,b);   //复杂度O(m*n)
    for(auto it:ret)cout<<it<<" ";
    cout<<endl;
    
    cout<<"algo 2"<<endl;
    ret = alg2(a,b);    //复杂度O(n)
    for(auto it:ret)cout<<it<<" ";
    cout<<endl;
    return 0;
}