文章

39

粉丝

74

获赞

1

访问

19.1k

头像
逆序对 题解:merge_sort
P1584 杭州电子科技大学机试题
发布于2024年3月14日 16:59
阅读数 603

#include <stdio.h>
#include <stdlib.h>

int q[100005],temp[100005];

int merge_sort(int q[],int l,int r){
    if(l>=r)return 0;
    int mid=(l+r)/2;
    int res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);

    int k=0;
    int i=l;
    int j=mid+1;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j])temp[k++]=q[i++];//正常
        else {
            res+=mid-i+1;
            temp[k++]=q[j++];//逆序
        }
    }
    while(i<=mid)temp[k++]=q[i++];
    while(j<=r)temp[k++]=q[j++];

    for(i=l,j=0;i<=r;i++,j++)q[i]=temp[j];
    return res;

}


int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    printf("%d\n",merge_sort(q,0,n-1));

    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发