逆序对问题

逆序对问题：在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对

刚刚看完左神的算法视频，对逆序对问题很快就有了思路，采用归并排序来解决问题，在每次的合并时判断合并集合左边是否比右边的数大如果比左边的大就打印出来。如果右边集合合并完了而左边集合还没合并完，说明左边剩余元素都比右边大，所以打印出左边所有剩余元素和右边的所有元素组成的逆序对。

代码如下：

public class test {
	
	public static void main(String[] args) throws UnknownHostException {
		int a[] = {1,10,2,9,5,4,7,3};
	     sort(a,0,a.length-1);
	     for(int i = 0; i<a.length ;i++){
	    	 System.out.println(a[i]);
	     }
	}
	 
   public static void sort(int a[],int l,int r){
	   if(l == r)
		   return ;
	   int mid = (l+r)/2;
	   sort(a,l,mid);
	   sort(a,mid+1,r);
	   merge(a,l,mid,r);  //合并数据
   }
   
   public static void merge(int a[],int l,int mid,int r){
	   int help[] = new int [r-l+1];	//用于暂时保存合并数据
	   int p1 = l,p2 = mid+1;
	   int i = 0;
	   int sum = 0;
	   while(p1 <= mid&& p2 <= r){
		   if(a[p1]>a[p2]){				//打印合并时的逆序对
			   System.out.println("["+a[p1]+","+a[p2]+"]");
		   }
		   help[i++] = a[p1]<a[p2] ? a[p1++] : a[p2++];  
	   }
	   while(p1 <= mid){		//将剩余元素直接拷贝给help
		   help[i++] = a[p1++];
		   for(int t = mid+1; t<=r;t++){
			   System.out.println("["+a[p1]+","+a[t]+"]");			//左边剩余元素都比右边大，打印所有
		   }
	   }
	   while(p2 <= r){
		   help[i++] = a[p2++];
	   }
	   for(int q = 0; q<help.length; q++){
		   a[q+l] = help[q];
	   }
   }
}