一，问题描述
给定一个数组，求解该数组中有多少组逆序对。比如 [7,5,6,4]一共有五对逆序对。分别是:(7,6)，(7，5)，(7，4)，(6，4)，(5，4)
二，算法分析
有两种方法来求解逆序对 的数目。一种是，对数组中的每个元素，都与它后面的元素进行比较，若后面的元素比它小，则找到一个逆序对。
这样，第一个元素与后面的n-1个元素比较，一共比较 n-1 次，第二个元素比较 n-2次，.....故一共需要比较 n(n+1)/2 次。时间复杂度为O(N^2)
另一种方式则是借助排序。试想，某些排序算法（归并、快速排序）只需要O(NlogN)就把整个数组排好序了，那能不能利用排序来求逆序对 的数目？
其实，排序过程，就是一个不断地消除逆序对 的过程。对于有序数组，它的逆序对为0。
而对于消除逆序对，在归并排序中，合并两个有序子数组的过程 就是一个消除逆序对的过程。
关于归并排序可参考：http://www.cnblogs.com/hapjin/p/5518921.html
因此，只需要对归并排序中的合并过程稍做修改，就可以求解逆序对的数目了。
三，代码实现及分析
1 public class InversePairs { 2 //求 arr[] 中逆序对的数目 3 public static int inversePairs(int[] arr) { 4 if (arr == null || arr.length <= 1)//特殊情况处理 5 return 0; 6 int[] tmpArr = new int[arr.length];//类似于 归并排序中用到的辅助数组 7 return inversePairs(arr, tmpArr, 0, arr.length - 1); 8 } 9 //类似于归并排序中的 递归分解数组 10 private static int inversePairs(int[] arr, int[] tmpArr, int left, int right) { 11 if (left < right) {//递归分割数组的退出条件,当数组中只有一个元素时(left==rigth)不需要再递归了 12 int currentPairs = 0; 13 int center = (left + right) / 2; 14 15 int leftPairs = inversePairs(arr, tmpArr, left, center);//左半部分数组的逆序对数目 16 int rightPairs = inversePairs(arr, tmpArr, center + 1, right);//右半部分数组的逆序对数目 17 currentPairs = merge(arr, tmpArr, left, center + 1, right);//合并左右部分数组时,消除的逆序对数目 18 return leftPairs + rightPairs + currentPairs; 19 } 20 return 0;// left==right 意味着子数组中只有一个元素.逆序对数目当然为0 21 } 22 //类似于 归并排序中的 合并两个有序子数组 23 private static int merge(int[] arr, int[] tmpArr, int leftPos, 24 int rightPos, int rightEnd) { 25 int leftEnd = rightPos - 1; 26 int numElements = rightEnd - leftPos + 1;//当前合并的元素个数 27 int tmpPos = leftPos; 28 29 int inverseCount = 0;//记录逆序对的数目 30 while (leftPos <= leftEnd && rightPos <= rightEnd) { 31 if (arr[leftPos] > arr[rightPos]) { 32 inverseCount += leftEnd - leftPos + 1; 33 tmpArr[tmpPos++] = arr[rightPos++]; 34 } else { 35 tmpArr[tmpPos++] = arr[leftPos++]; 36 } 37 } 38 39 while (leftPos <= leftEnd) 40 tmpArr[tmpPos++] = arr[leftPos++]; 41 while (rightPos <= rightEnd) 42 tmpArr[tmpPos++] = arr[rightPos++]; 43 44 for (int i = 0; i < numElements; i++, rightEnd--) 45 arr[rightEnd] = tmpArr[rightEnd]; 46 return inverseCount; 47 } 48 //for test purpose 49 public static void main(String[] args) { 50 int[] arr = {2,1,4,3}; 51 int result = inversePairs(arr); 52 System.out.println(result); 53 } 54 }
其实，上面整个过程 与归并排序的实现非常的相似。最重要的是第32行，计算逆序对数目。（与归并排序比较，最主要的变化的也是第32行）
当 merge 两个 数组时：请注意，这两个数组是有序的。因此，逆序对的数目计算公式为：leftEnd - leftPos + 1
比如，如下示例：对于 5 而言，比4大。这说明 5 后面的元素都比 4 大。因此，对于 4 而言有 (5,4) (7,4)两个逆序对。
另外，第15行-17行，也是对递归的理解（归并排序是一个递归过程，计算逆序对数目 也是一个递归过程）
int leftPairs = inversePairs(arr, tmpArr, left, center);//左半部分数组的逆序对数目
int rightPairs = inversePairs(arr, tmpArr, center + 1, right);//右半部分数组的逆序对数目
currentPairs = merge(arr, tmpArr, left, center + 1, right);//合并左右部分数组时,消除的逆序对数目
return leftPairs + rightPairs + currentPairs;//最终返回 总的逆序对 的数目
四，参考资料
