数组中的逆序对

编程练习

题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

思路：一开始想到的方法是全遍历，每个元素都和它之后的元素比较大小，如果前边的大于后边的就让逆序对的值加一，这个算法的时间复杂度是o(n2),最后运行超时了。

　　然后就考虑改进算法，在网上查看了好多相关算法，最后选择了归并排序，总体思想就是将一个大的数组分成两个小的数组，在这两个小数组里分别进行递归排序。比如对于数组[7,5,6,4]，可以将数组分为[7,5]和[6,4]，很显然对于前一个数组中的逆序对数为1，后一个数组中的逆序对数也为1，和为2。然后为了统计这两个数组合并后的逆序对数，可以想到的方法是对两个数组分别做从大到小的排序，这样就可以将上述两个数组变为[5,7]和[4,6]。注意：这样做的好处是可以从第一个数组的最后一个位置和第二个数组的最后一个位置开始比较，比如7和6进行比较，发现7大于6，那么因为两个数组都是排好序的，所以7大于第二个数组中的每一个元素，这样的话逆序对数就增加第二个数组的元素个数，在这个例子里就是2，然后再依次比较倒数第二个元素5和[4,6]的大小关系，可以得到5小于6但是大于4，所以逆序对数再加1，这样分开比较的时候逆序对数为3再加上之前的每个数组里的逆序对数和为2，所以总的逆序对数为5。

　　要注意的点：就是归并排序统计得到了数组间的逆序对数目以后需要借助一个辅助数组来对合并后的数组从小到大排序，为了使这个大的数组在作为更大的数组的分数组时是递增的，可以方便递归排序。

java代码如下：

public class InversePairs2 {
	int count=0;
    public  int InversePairs(int [] array) {
       
    	if(array==null && array.length==0) {
    		return 0;
    	}
    	mergeSort(array,0,array.length-1);
    	return count;
    }
    public void mergeSort(int [] array,int start,int end) {
    	if(start<end) {
    		int mid=(start+end)/2;
    		//分成两部分做递归
    		mergeSort(array,start,mid);
    		mergeSort(array,mid+1,end);
    		
    		int i=mid;
    		int j=end;
    		int t=0;
    		int [] temp=new int [end-start+1];// 辅助数组，用来给统计完数组对间的逆序对数后对合并后的数组进行排序(由小到大)
    		
    		while(i>=start && j>=mid+1) {
    			if(array[i]>array[j]) {
    				count+=j-mid;
    				temp[t]=array[i];
    				t++;
    				i--;
    			}else {
    				temp[t]=array[j];
    				t++;
    				j--;
    			}
    			if(count>=1000000007) {
    				count%=1000000007;
    			}
    		}
    		//将剩余的元素放入temp数组中
    		while(i>=start) {
				temp[t]=array[i];
				t++;
				i--;
			}
			while(j>=mid+1) {
				temp[t]=array[j];
				t++;
				j--;
			}
			for(int c=start;c<=end;c++) {
				array[c]=temp[end-c];
			}
    	}
    }
    public static void main(String[] args) {
		int [] arr= {1,2,3,4,5,6,7,0};
		InversePairs2 ip=new InversePairs2();
		System.out.println(ip.InversePairs(arr));
	}

}