|
今天学习算法导论第二章中提到的逆序对问题，思前想后采用2种方式比较妥当。具体见下述分析。
逆序对问题：
逆序对（inversion pair）是指在序列{a0,a1,a2...an}中，若ai<aj(i>j)，则(ai,aj)上一对逆序对。而逆序数 （inversion number）顾名思义就是序列中逆序对的个数。例如： 1 2 3是顺序，则逆序数是0；1 3 2中(2,3)满足逆序对的条件，所以逆序数只有1； 3 2 1中(1,2)(1,3)(2,3)满足逆序对，所以逆序是3。由定义不难想象，序列n的逆序数范围在[0,n*(n-1)/2]，其中顺序时逆序数为 0，对于一个倒序的自然序列{an,an-1,an-2.......3,2,1}来说，是一个完全逆序序列。根据定义我们可以很方便的得到该序列的逆序对总数为 T(N)=∑(i,i<=n)fn,其中fn=(n-1)得到最终结果为T(N)=N*(N-1)/2.
就我所知，目前求这种逆序对最快的算法是利用归并排序，其时间复杂度为O(nlgn), 空间复杂度为O(n)
这里我给出一个O(n*n)的循环算法和一个O(nlgn)的分治算法。
- 循环算法，见下面代码：
public int countByLoop(Integer a[]){
int count=0;
for(int i=0;i<a.length;i++){
for(int j=a.length-1;j>i;j--){
if(a[i]>=a[j]){
count++;
System.out.printf("found=(i=%d,j=%d,a[i]=%d,a[j]=%d)\n",i,j,a[i],a[j]);
}
}
}
return count;
}
2. 分治算法实现如下
public int count(Integer a[],int low,int high){
int count=0;
if(low<high){
int mid=(low+high)/2;
count+=count(a,low,mid); //分治先计算左边的数组
count+=count(a,mid+1,high); //计算右边的数组
count+=mergeCount(a,low,mid,high); //合并两个结算结果
}
return count;
}
/**
* 采用分治法求得逆序对
* @param a
* @return
*/
public int count(Integer a[]){
return count(a,0,a.length-1);
}
private int mergeCount(Integer[] a, int low, int mid, int high) {
int count=0;
int i=low;
int j=mid+1;
while(i<=mid&&j<=high){
if(a[i]<=a[j]){
i++;
}else{
count+=mid-i+1;
for(int k=i;k<=mid;k++){
System.out.printf("(%d,%d)\n",a[k],a[j]);
}
j++;
}
}
while(i<=mid)i++;
while(j<=high)j++;
return count;
}
看到上述的算法，是不是觉得很眼熟呢，不错，其实和我们熟悉的归并排序算法很相似，只是这里不需要额外的辅助内存空间来保存排序
欢迎各位拍砖
| 
转播
