求逆序对的三种方法

大家好，我是讯享网，很高兴认识大家。

逆序对的定义：对序列
讯享网，存在且，那么这是一个逆序对

第一种：暴力求解

第二种：归并排序

第三种：树状数组

第一种：暴力求解

N^2 暴力，这里我就不写了。

第二种：归并排序

归并排序的原理就是将一个序列无限二分，直到每个部分只有一个元素，那这部分就是有序的了，再对两个元素就行比较排序，分别放入左半部分和右半部分；对左半部分和右半部分分别进行有序插入后合并，如此反复......

例如，我们现在有两个部分：

1 3 5 7 9

2 4 6 8 10

现在进行合并，对两个部分的第一个数进行比较。

因为 1 < 2，所以将 1 放入临时数组（也就是答案数组），这时临时数组只有一个元素

然后因为 3 > 2，所以将 2 放入临时数组，这时临时数组有两个元素

1 2

然后因为 3 < 4，所以将 3 放入临时数组，这是临时数组有三个元素

1 2 3

......

如此反复，最后得到的临时数组有十个元素

1 2 3 4 5 6 7 8 9 10

那么我们再来看一下逆序对是怎么求的，在第三步之后，我们需要比较 4 和 5 的大小，因为 4 小于 5 ，又因为左半部分数组是有序（递增）的，所以左半部分剩下的所有元素均大于 4 ，也就是说左半部分剩下的所有数均可以和 4 构成逆序对，左半部分剩下元素 5 7 9 三个元素，所以对 4 而言，有三个逆序对（5，4）（7，4）（9，4），其余同理......

实现代码：

#define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> using namespace std; #define int long long int n, ans = 0; int a[], temp[]; void merge_pai(int l, int r, int mid) { int i = l, p = l, j = mid; while (i < mid && j <= r) { if (a[i] <= a[j]) temp[p++] = a[i++]; else { temp[p++] = a[j++]; ans += mid - i;//核心，逆序对在这里 } } while (i < mid) temp[p++] = a[i++];//防止a[]中前面的数还没有移完 while (j <= r) temp[p++] = a[j++];//防止a[]中后面的数还没有移完 p = i = l; while (p <= r) a[i++] = temp[p++];//转移到a[]中 } void merge_sort(int l, int r) { if (l < r) { int mid = (l + r) / 2; merge_sort(l, mid); merge_sort(mid + 1, r); merge_pai(l, r, mid + 1); } } signed main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; merge_sort(1, n); cout << ans << endl; }

讯享网

第三种：树状数组

树状数组的原理我就不阐述了。

树状数组是用来区间求和的，可以快速求出一段区间内的数的和。

那么我们应该怎样利用这个性质呢？

对于一个数，如果比它大的数在它之前出现，那么这是一对逆序对。

那么我们在对某个数进行统计时，我们需要统计一下比它大并且在它之前出现的数，这个时候我们就可以使用 tree 数组进行标记，如果一个数出现过了，我们将相应的 tree 数组标记为 1 ，（例如第一个数为 1 ，那么我们将 tree[1] 标记为 1 ，第二个数为 4 ，那么我们将 tree[4] 标记为1 ......）。

例如，我们对数组进行O(n)遍历，将遍历到的数标记为 1 ，表示出现过

原数组	1 4 3 5 6 2
遍历第一次后的 tree 数组	1 0 0 0 0 0
遍历第二次后的 tree 数组	1 0 0 1 0 0
遍历第三次后的 tree 数组	1 0 1 1 0 0
遍历第四次后的 tree 数组	1 0 1 1 1 0
遍历第五次后的 tree 数组	1 0 1 1 1 1
遍历第六次后的 tree 数组	1 1 1 1 1 1

我们在遍历第三次时，此时 a_3 = 3，标记 tree[3] = 1，对区间 [1, 3] 求和，sum[1~3] = tree[1] + tree[2] + tree[3] = 2，然而我们在进行第三次遍历，所以此时应该有三个数，但求和发现范围 1~3目前只有两个数出现过（因为sum[1~3] = 2），说明还有一个数我们没有找到，我们是对区间 [1, 3] 求和，所以还有一个数应该比 3 大并且在 3 之前出现，所以这是一个逆序对，其他同理......

对于第次遍历（ a_m ）时，如果 sum[1,a_m]=k ，那么 a_m 作为第二个数时的逆序对有 m-k 对

实现代码：

讯享网#define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> using namespace std; #define int long long const int N = 5e6 + 10; int tr[N * 2], n; int lowbit(int x) { return x & (-x); } void add(int x, int v) { while (x <= n) {//这里的n是最大值，必要时需要进行离散化 tr[x] += v; x += lowbit(x); } } int sum(int x) { int ans = 0; while (x) { ans += tr[x]; x -= lowbit(x); } return ans; } signed main() { int ans = 0; cin >> n; for (int i = 1; i <= n; i++) { int v; cin >> v; add(v, 1); ans += i - sum(v); } cout << ans << endl; }

求逆序对的三种方法

第一种：暴力求解

第二种：归并排序

第三种：树状数组

相关推荐