利用分治策略求逆序数
逆序数:一个数列arr[N],对任意两个数,如果前面的数大于后面的数,那么就称它们为一对逆序数。一个一维数组中,逆序的个数就是要求的逆序数
- 伪代码描述
INPUT:一个一维数组 arr[n]
OUTPUT:逆序数的数量
- C++代码实现
#define N 15
int sum=0;
int sum1=0;
void Merge_CountInversion(int a[],int l,int m,int r)
{
int i=l;
int j=m+1;
int k=0;
int resu[N]={0};
while((i<=m)&&(j<=r))
{
if(a[i]<a[j])
{
resu[k]=a[i];
i++;k++;
}
else
{
resu[k]=a[j];
sum+=(m-i+1);
k++;j++;
}
}
while(i<=m)
{
resu[k]=a[i];
k++;i++;
}
while(j<=r)
{
resu[k]=a[j];
k++;j++;
}
for(i=0;i<k;i++)
{
a[l++]=resu[i];
}
}
void Merge_Sort(int a[],int l,int r)
{
int m;
if(r-l>=1)
{
m=(r+l)/2;
Merge_Sort(a,l,m);
Merge_Sort(a,m+1,r);
Merge_CountInversion(a,l,m,r);
}
}