文章
39
粉丝
74
获赞
1
访问
18.5k
#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;
}
登录后发布评论
暂无评论,来抢沙发