下面是使用java实现的递归逆序对查找，所谓的逆序对就是在数组A[]中如果 i < j ,并且A[i] > A[j], 则我们说A[i]和A[j]是一对逆序对。如果用普通的算法实现的话，查找的时间复杂度，是O(N*N)，使用这里的队规的方式查找的话，时间复杂度是O(N*lgN)
import java.util.Date;
import java.util.Random;
/*
* 使用递归实现的统计数组中的逆序对数量。
*/
public class InversionSearch {
public static void main(String args[])
{
int len = 5;
Date date = new Date();
Random random = new Random(date.getSeconds());
int data[]=new int[len];
for(int i = 0; i < len; i++)
{
data[i]=(int)(random.nextFloat()*100+1);
}
show(data);
int count= inversionSearch(data,1,data.length);
System.out.println("共有逆序对："+count);
}
private static void show(int[] data)
{
System.out.println("========================");
for(int i = 0; i < data.length; i++)
{
System.out.print(data[i] + " ");
}
System.out.println();
System.out.println("========================");
}
public static int inversionSearch(int[] data,int start,int end)
{
int count=0;
if(end>start){
int pos = (start+end)/2;
int temp1 = inversionSearch(data,start,pos);
int temp2 = inversionSearch(data,pos+1,end);
count = mergeSearch( data,start,pos,end)+temp1+temp2;
}
return count;
}
public static int mergeSearch(int[] data,int start,int pos,int end)
{
int count=0;
for(int i=pos; i<end; i++)
{
for(int j=start-1; j<pos; j++)
{
if(data[i]<data[j])
{
count++;
}
}
}
return count;
}
}
