归并排序

思想

1.确定分界点mid=l+r>>1
2.递归分治求解左右子问题
3.合并已排好的子区间

https://visualgo.net/en/sorting

算法模板

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;//只有一个元素

    int mid = l + r >> 1;//1.取分界中间点
    merge_sort(q, l, mid);//2.递归分别求解
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;//k=0,重新给temp[]赋值，记录l,r区间内排好序的数 
    while (i <= mid && j <= r){//将区间进行合并，用两个指针分别指向两个区间(左边界)，逐个比较，将两个区间上指针所指的小的元素插入到
    //temp数组中，移动相应指针，继续比较插入
     if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];   
    }
    //若有一个区间已经添加完毕 则将另一个区间剩余元素直接插入到temp数组后面
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//每次将l,r区间内的数排好序赋值给q[i]; 
}

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int q[N],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);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]){
            temp[k++]=q[i++];
        }else{
            temp[k++]=q[j++];
        }
    }
    while(i<=mid){
        temp[k++]=q[i++];
    }
    while(j<=r){
        temp[k++]=q[j++];
    }
    for(int i=l,j=0;i<=r;i++,j++){
        q[i]=temp[j];
    }
} 
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    int l=0,r=n-1;
    merge_sort(q,l,r);
    for(int i=0;i<n;i++){
        cout<<q[i]<<' ';
    }
    cout<<endl;
    return 0;
}