寻找逆序对
/** Let A be an array of n distinct numbers,If i<j and a>a,
* then pair(i,j) is called an inversion of A .This program determies
* the number of inversions of n elements in o(nlgn) worst-case time
*/
#include<stdio.h>
#include<malloc.h>
int count(int a[],int low,int middle,int high)
{
int number=0;//count the inversion
int llen=middle-low+1;
int hlen=high-middle;
int *L = (int *)malloc((llen+1)*sizeof(int));
int *H = (int *)malloc((hlen+1)*sizeof(int));
int i=0;
for(;i<llen;i++)
L=a;
L=99999;
i=0;
for(;i<hlen;i++)
H=a;
H=99999;
int k=low;
i=0;
int j=0;
for(;k<high+1;k++)
{
if(L>H)
{
a=H;
number+=llen-i;
}
else
{
a=L;
}
}
free(L);
free(H);
return number;
}
int Count_inversion(int a[],int l,int h)
{
int num=0,middle;
if(l>=h) return 0;
if(l<h)
{
middle=l+(h-l)/2;
num+=Count_inversion(a,l,middle);
num+=Count_inversion(a,middle+1,h);
num+=count(a,l,middle,h);
}
return num;
}
int main()
{
int a={1,6,3,4};
int c=Count_inversion(a,0,3);
printf("the number of inversions is %d\n",c);
return 0;
}
页:
[1]