求逆序对

归并排序求逆序对：

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[1005];//存放数组  
int rr[1005];//辅助数组，额外开销 
int n,ans;
void build(int l,int r)
{
	int mid=(l+r)/2;
	if(l==r) return;//只有一个数的时候返回 
	build(l,mid);//不断分割 
	build(mid+1,r); 
	int x=l,y=mid+1,z=l;
	while(x<=mid&&y<=r)
	{
		if(a[x]<a[y])
		rr[z++]=a[x++];
		else 
		rr[z++]=a[y++],ans+=mid-x+1;//逆序对 
	}
	while(x<=mid)
	rr[z++]=a[x++];
	while(y<=r)
	rr[z++]=a[y++];
	for(int i=l;i<=r;i++)
		a[i]=rr[i];
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		scanf("%d",a+i);
	build(0,n-1);
	cout<<ans<<endl; 
}