寻找逆序对

javayestome

/*
* Let A[1...n] be an array of n distinct numbers,If i<j and a[i]>a[j],
* 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[i]=a[low+i];
L[i]=99999;
i=0;
for(;i<hlen;i++)
  H[i]=a[middle+i+1];
H[i]=99999;
int k=low;
i=0;
int j=0;
for(;k<high+1;k++)
{
  if(L[i]>H[j])
  {
   a[k]=H[j++];
   number+=llen-i;
  }
  else
  {
   a[k]=L[i++];
  }
}
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[4]={1,6,3,4};
int c=Count_inversion(a,0,3);
printf("the number of inversions is %d\n",c);
return 0;
}