归并排序

CR__7 · 2021-01-28 15:45:06 · 个人记录

归并排序

[模板]

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>

using namespace std;
int n,a[1234],b[1234];
void merge_sort(int l,int r)
{
    if(l==r) return;//只剩一个数，不用排序
    int mid=(l+r)/2;
    //分解： 
    merge_sort(l,mid);//左半部分排序 
    merge_sort(mid+1,r);//右半部分排序
    //合并到b:
    int  p1=l,p2=mid+1;//p1:左半部分起始点 
    for(int i=l;i<=r;i++)//p2：右半部分起始点 
    {
        if(p1>mid) b[i]=a[p2++];//如果左半部分没数，加入右半部分 
        else if(p2>r) b[i]=a[p1++];//如果右半部分没数，加入左半部分 
        else if(a[p1]<a[p2]) b[i]=a[p1++];//如果都有，加入最小数 
        else b[i]=a[p2++];
    }
    //转移到a: 
    for(int i=l;i<=r;i++)
        a[i]=b[i];

}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    merge_sort(1,n);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}