归并排序

归并排序,是将区间分为两部分,先对小的区间进行排序,然后再合并到大的区间中,最后实现全部排好序。

#include<bits/stdc++.h>
using namespace std;
int a[100010],temp[100010];
void merge(int L,int R){  //对区间进行划分成前两半和后两半
    int mid=(L+R)>>1;
    int k=1,l=L,r=mid+1;
    while(l<=mid&&r<=R){
        if(a[l]<=a[r])  temp[k++]=a[l++];
        else{
            //这里可以用来求逆序对 sum+=(mid-l+1) 
            temp[k++]=a[r++];
        }
    }
    while(l<=mid) temp[k++]=a[l++];
    while(r<=R) temp[k++]=a[r++];
    for(int i=L,k=1;i<=R;i++,k++){
        a[i]=temp[k];
    }
}
void mergesort(int l,int r){
    if(l<r){   //注意这里的条件
        int mid=(l+r)>>1;
        mergesort(l,mid);
        mergesort(mid+1,r);
        merge(l,r);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)  cin>>a[i];
    mergesort(0,n-1);
    for(int i=0;i<n;i++)  cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}
全部评论

相关推荐

05-16 11:16
已编辑
东华理工大学 Java
牛客737698141号:盲猜几十人小公司,庙小妖风大,咋不叫她去4️⃣呢😁
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务