1.逆序对概念
设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。
2. 计算数组中逆序对个数
方法一：逐个遍历，复杂度O(n^2)
Java实现如下：
public static int reverseCoupleNum1(char[] str) { int cnt=0; for(int i=0;i<str.length-1;i++) { for(int j=i+1;j<str.length;j++) { if(str[i]>str[j]) cnt++; } } return cnt; }
方法二：利用归并排序中的归并过程对逆序对进行计数，复杂度O(nlgn)
Java实现如下：
public static int mergeSort(char[] str,int p,int q) { if(p>=q) { return 0; } else { int cnt1=0,cnt2=0,cnt=0; int middle=(p+q)/2; cnt1=mergeSort(str,p,middle); cnt2=mergeSort(str,middle+1,q); char[] l=new char[middle-p+1]; char[] r=new char[q-middle]; System.arraycopy(str, p, l, 0, l.length); System.arraycopy(str, middle+1, r, 0, r.length); //process of merge int lpos=0,rpos=0; for(int i=p;i<=q;i++) { if(lpos<l.length&&rpos<r.length) { if(l[lpos]>r[rpos]) { str[i]=r[rpos++]; cnt+=l.length-lpos;//KEY POINT } else { str[i]=l[lpos++]; } } else if(lpos<l.length) { str[i]=l[lpos++]; } else { str[i]=r[rpos++]; } } return cnt+cnt1+cnt2; } }
