归并排序
完成归并并求出逆序对数的代码如下
#include<bits/stdc++.h>
using namespace std;
//a存储原数组和最后排序完的数组，c存储每次归并排序的数组
int n,a[500010],c[500010];
long long ans;
//b，e表示需要排序的位置范围
void msort(int b,int e)//归并排序
{
if(b==e)
return;
//i是左区间的下标，j为右区间的下标，k是数组c中的位置
int mid=(b+e)/2,i=b,j=mid+1,k=b;
msort(b,mid),msort(mid+1,e);//归并的体现
//左右区间中都还有数，则继续比较
while(i<=mid&&j<=e)
if(a[i]<=a[j])
c[k++]=a[i++];
else
c[k++]=a[j++],ans+=mid-i+1;//统计答案，因为归并时左右两个区间各自已经有序
//右区间没有数左区间还有
while(i<=mid)
c[k++]=a[i++];
//左区间没有数右区间还有
while(j<=e)
c[k++]=a[j++];
//将排序好的数覆盖到原数组中
for(int l=b;l<=e;l++)
a[l]=c[l];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
msort(1,n);
printf("%lld",ans);
return 0;
}
