逆序对算法的定义:对于一个给定的数列{An},如果有i<j,且Ai>Aj,则称(i,j)为一逆序对.这是一个很奇妙的算法,大家有时间一定要研究下,下面一起来看看吧 。
我们目前要解决的问题是,给出一个数列,求出这个数列包含多少个逆序对
solution 1:最原始的方法,就是列举,两重循环,代码:
int count_inversion(int *a,int N)
{
int count = 0;
int i,j;
for (i = 0 ;i < N ;i ++)
for(j = i + 1; j < N ;j++)
if (a[i] < a[j])
count ++;
return count;
}
这种时间复杂度是O(n^2)
不过还有更好的算法,树上提示用mergesort,可以达到o(nlogn),于是,我修改了mergesort代码:
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);
}
修改这一行就可以了,这种算法甚是巧妙。
责任编辑:小草