Question

跪求：如何在O(nlgn)的时间内，利用顺序统计树对大小为n的数组中的逆序对进行计数。 VC++6.0详细代码。

Answer 1

就是在归并排序的同时计算逆序对
void merge_inversion(int *a,int l,int m,int r)
{
int i,j,k;
int n1 = m - l + 1;
int n2 = r - m;
int *L = (int *)calloc(sizeof(int),n1);
int *R = (int *)calloc(sizeof(int),n2);
for(i = l; i <=m ;i ++)
L[i-l]=a[i];
for(j = m +1 ;j <= r ;j ++)
R[j -m-1] = a[j];
i = 0 ;
j = 0 ;
for(k = l ;k <= r ;k ++)
{
if ( i < n1 && j < n2 )
{
if( L[i] < R[j])
{
a[k]=L[i++];
globa_count += n2-1-j+1;
}
else
a[k]=R[j++];
}
else
break;
}
// process if one part terminately early
if (i == n1 && j < n2)
while(j < n2)
a[k++]=R[j++];
if (i < n1 && j == n2)
while(i < n1)
a[k++]=L[i++];
free(L);
free(R);
}