数组之数组中的逆序对

1.本题知识点

   归并排序

2. 题目描述

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

3. 思路

   ① 归并排序，不会的请跳到我的基础算法博客查看。

   ② 归并过程中，排序的同时记录逆序对的个数。

   Java版本：

/** * 切分和合并，顺便记录逆序对count */ public int SplitAndMerge(int [] array, int left, int right, int [] temp) { //校验 if(array == null || array.length == 0 ) return 0; //终止条件 if(left < right){ //1.切分过程 int mid = (left + right) >> 1; //切分点 int leftCount = SplitAndMerge(array, left, mid, temp)%1000000007; int rightCount = SplitAndMerge(array, mid+1, right, temp)%1000000007; // merge(array, left, right, mid, temp,count); 大错特错的传递方式,基本数据类型count传递是不能改变其值的！！！ //2.合并过程 int count = 0;//逆序对的计数 int i = left; //左子序列的指针 int j = mid +1;//右子序列的指针 int t = 0 ; //临时数组的指针，空间换时间 while(i <= mid && j <= right){ if(array[i] <= array[j]){ temp[t++] = array[i++]; } else{ temp[t++] = array[j++]; //★核心理解：归并排序中2个子序列是升序从小到大进行比较的 //若array[i] > array[j]，则array[i] ~ array[mid]都会大于arr[j]，所以都属于逆序对 count += mid - i +1 ; if(count >= 1000000007){ count = count % 1000000007; } } } while(i <= mid){ temp[t++] = array[i++]; } while(j <= right){ temp[t++] = array[j++]; } t=0; //将temp数组copy回原数组 while(left <= right){ array[left++] = temp[t++]; } return (leftCount + rightCount + count)%1000000007; } return 0; } //调用 public int InversePairs(int [] array) { return SplitAndMerge(array, 0, array.length -1, new int[array.length]); }