【博客327】求逆序对的数量

内容： 记录求一组数中逆序对的数量

思路：

1、采用分治的思路 2、每次对区间分为前一半和后一半来求解 3、每次子区间求解完后都是有序的 4、由于每次对子区间求解完后是有序的，那么大区间求解的时候只需要采用一种比较方法： 从后往前，因为子区间是有序的，所以当前子区间的遍历的那个数若比另一个子区间的最后一个数大， 那么肯定就比前面所有的都大，因为子区间是有序的，此时逆序对的数量增加的值就是与你比较的子 区间的数字前面的元素个数。如果当前子区间的遍历的那个数若比另一个子区间的最后一个数小，那么 就可以继续遍历与你比较的目标区间的下一个数字了，因为你当前已经是最大的数，而与你比较的区间 的当前遍历的数还比你大，那你其它的肯定都比它小，就无须再比较，肯定不能增加逆序对数量的值

代码：

/* 求逆序对数量 */ #include<iostream> #include<vector> using namespace std; long long InversePairsCore(vector<int> &data, vector<int> &copy, int start, int end) { if (start == end) { copy[start] = data[start]; return 0; } int length = (end - start) / 2;//是减不是加 long long left = InversePairsCore(copy, data, start, start + length); long long right = InversePairsCore(copy, data, start + length + 1, end); int i = start + length; int j = end; int indexcopy = end; long long count = 0; while (i >= start && j >= start + length + 1) { if (data[i] > data[j]) { copy[indexcopy--] = data[i--]; count = count + j - start - length; } else { copy[indexcopy--] = data[j--]; } } for (; i >= start; i--) copy[indexcopy--] = data[i]; for (; j >= start + length + 1; j--) copy[indexcopy--] = data[j]; return left + right + count; } int InversePairs(vector<int> data) { int length = data.size(); if (length <= 0) return 0; vector<int> copy; for (int i = 0; i < length; i++) copy.push_back(data[i]); long long count = InversePairsCore(data, copy, 0, length - 1); return count ; } int main() { vector<int> input; int n; cin >> n; for (int i = 0; i < n; i++) { int number; cin >> number; input.push_back(number); } int count=InversePairs(input); cout << count << endl; }