在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P
简单思路是，挨个遍历数组中的元素，每遍历到一个元素之后和后面的元素再逐一比较，这样的复杂度是O(n^2)。 这里时间都花费在了逐一比较上，这样一个个找逆序对显然是比较耗时的。归并排序的思路就是一次性的找出一串来，所以复杂度会低很多，本质就是归并排序的复杂度O(nlogn)。 首先写一个归并排序，只需要做一丁点修改就可以找出逆序对。归并排序假设左右两个子数组都是有序的，然后再merge成一个大的数组，在merge的过程中，如果前面子数组中某一元素的比后面子数组的某个元素大，那么他肯定后面子数组这个元素之前的所有数都要大，也就是都形成了逆序对，这样一来，一次性就找出了一串逆序对，而不是一个个的找。 另外注意，我们一边找逆序对，一边还要排序，这样做是为了防止重复找已经找到的逆序对。
int merge(vector<int> &data, int start, int mid, int end) { vector<int> tmp; int i = start; int j = mid+1; // 右半部子数组开头是mid+1，因为下面右半部子数组不包含mid int cnt = 0; while(i <= mid && j <= end) { if(data[i] <= data[j]) { tmp.push_back(data[i]); i++; } else { cnt += j-mid; // 逆序对，从j开始一直到第二个子数组的头部，都够成了逆序对 tmp.push_back(data[j]); j++; } } // 剩余的子数组merge到tmp while(i <= mid) { tmp.push_back(data[i]); i++; } while (j <= end) { tmp.push_back(data[j]); j++; } for(i=0; i<tmp.size(); i++) // 还需要将排序好的数组复制回原数组 data[start+i] = tmp[i]; return cnt; } int mergeSort(vector<int> &data, int start, int end) { int cnt = 0; if(start < end) { int mid = (start + end)/2; cnt += mergeSort(data, start, mid); //左半部分 包含mid cnt += mergeSort(data, mid+1, end); //右半部分 不包含mid cnt += merge(data, start, mid, end); //合并两部分，并计算数量 } return cnt; } int InversePairs(vector<int> &data) { return mergeSort(data, 0, data.size()-1); }