AcWing 787. 归并排序

⬅ 返回

1.原题链接

链接

2.代码

// step1 将n个元素分成两个含n/2元素的子序列
// step2 用归并排序将两个子序列递归排序
// step3 合并两个已排好的子序列
#include <iostream>
using namespace std;
const int N=1e6;
int a[N];
 
void marge_sort(int a[],int l,int r)
{
    int b[N];
    if(l>=r)return;
    int mid=(l+r)/2;
    marge_sort(a,l,mid);marge_sort(a,mid+1,r);
    int i=l,j=mid+1,k=0;//i从L开始 j从mid+1开始
    while(i<=mid && j<=r)//这里有等号
    {
 
        if(a[i]>a[j])
        b[k++]=a[j++];
        else
        b[k++]=a[i++];
    }
    while(i<=mid)
    b[k++]=a[i++];
    while(j<=r)
    b[k++]=a[j++];
 
    for(i=l,j=0;j<k;i++,j++)//这一步最重要 决定了用b数组更新a数组中的位置 b数组也可以是全局变量
    a[i]=b[j];
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
     marge_sort(a,0,n-1);
     for(int i=0;i<n;i++)
         cout<<a[i]<<" ";
}