归并排序

归并排序算法作为排序算法之一，它是拥有一个比较固定的模板的。
算法的步骤分为以下几点

首先打散数组，然后对打散的数组的两端进行比较，然后存入到一个新的数组里面。
时间复杂度是 O(nlogn)

模板

#include<iostream>
using namespace std;
const int N=100010;
int n,k;
int q[N];
int temp[N];
void merge_sort(int q[],int l,int r){
    //思想就是从中间开始分隔数组
    if(l>=r) return;

    int mid=l+r>>1;
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);//如果在这个地方打散数组 mid就每次都会发生变化

    int i=l,j=mid+1;//如果是两个元素的话 l=0 r=1 mid=0 向下取整 所以j是0+1 这样不会有边界问题
    k=0;
    //如果在这个地方开始递归 mid每次都会发生变化
    // merge_sort(q,l,mid),merge_sort(q,mid+1,r);//如果在这个地方打散数组 mid就每次都会发生变化
    //开始归并
    while(i<=mid&&j<=r){
        if(q[i]<q[j]) temp[k++]=q[i++];//每一次存放的temp不是最终的temp k=0
        else temp[k++]=q[j++];
    }
    //如果还有元素没有放入到temp 那么一定是最后面的大数
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];
    //for(int i=0;i<n;i++) q[i]=temp[i];
    for (i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];//递归往回的时候不是每一次i都是0  但每一次都是l
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>q[i];
    merge_sort(q,0,n-1);

    for(int i=0;i<n;i++) cout<<q[i]<<" ";
    return 0;
}