算法导论学习之第二章-寻找逆序对

     今天学习算法导论第二章中提到的逆序对问题，思前想后采用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)的分治算法。

 

 

 

 

1.       循环算法，见下面代码：

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;
	}

 

  看到上述的算法，是不是觉得很眼熟呢，不错，其实和我们熟悉的归并排序算法很相似，只是这里不需要额外的辅助内存空间来保存排序

 

  欢迎各位拍砖