[C++知识库]归并排序*

基本思想

当不断二分二分拆到只有一个数的时候，就到了递归出口
然后及时排好局部顺序 再慢慢扩展

最重要的还是理解递归的过程，算法中间的过程要理解
每次递归 会进入下一个子函数 但是会保存现有的状态等子递归结束回来

代码模板

两两比的话  两组数不等长  一方多余的部分数就直接插
（直接看代码）

#include<iostream>
using namespace std;

int n;
const int N=1e5+10;
int q[N],t[N];

void g(int l,int r,int q[])
{
    if(l>=r) return;
    int mid=l+r>>1,k=0;
    int i=l,j=mid+1;
    g(i,mid,q);g(j,r,q);
    while(i<=mid&&j<=r)
    {
        if(q[i]<q[j]) t[k++]=q[i++];
        else t[k++]=q[j++];
    }
    while(i<=mid) t[k++]=q[i++];
    while(j<=r) t[k++]=q[j++];
    
//t只是临时数组，所以要换回q 调整好q的位置
k=0;//下面的lr是当前某个部分的起始和终止 一定要注意 
     while(l<=r) q[l++]=t[k++];
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>q[i];
    g(0,n-1,q);
    for(int i=0;i<n;i++) cout<<q[i]<<" ";
    return 0;
}

我错的问题

数组c++传参 int q[] 再写int q 就剁手