在数组a中如果a[i]>a[j].且i<j则<i,j>称为一个逆序数对
#include<iostream>
using namespace std;
#define MAX 1000;
void main()
{ int Calculate(int *A,int begin,int end,int mid);
int CountInversions(int *A,int begin,int end);
int A[5]={5,4,3,4,1};
int result=CountInversions(A,0,4);
cout<<result<<endl;
char f;
cin>>f;
}
int CountInversions(int *A,int begin,int end)
{ int Calculate(int *A,int begin,int end,int mid);
int count=0;
if(begin<end)
{
int mid=(begin+end)/2;
count+=CountInversions(A,begin,mid);
count+=CountInversions(A,mid+1,end);
count+=Calculate(A,begin,end,mid);
}
return count;
}
int Calculate(int *A,int begin,int end,int mid)
{
int cnt=0;
//bool counted=false;
int n1=mid-begin+1;
int n2=end-mid;
int *L=new int[n1+1];
int *R=new int[n2+1];
for(int m=0;m<n1;m++)
{
L[m]=A[begin+m];
}
for(int m=0;m<n2;m++)
{
R[m]=A[mid+1+m];
}
L[n1]=MAX;
R[n2]=MAX;
int i=0;
int j=0;
for(int k=begin;k<=end;k++)
{
if(L[i]<=R[j])
{ A[k]=L[i];
i++;
}
else
{ A[k]=R[j];
j++;
cnt=n1-i+cnt;
}
}
delete[]L;
delete []R;
return cnt;
}