一、引入
我们思考这样一个问题：
对于给定的一段正整数序列，逆序对就是序列中 ai > aj且 i < j 的有序对。 输入说明 第一行，一个数 n，表示序列中有 n 个数。 第二行 n 个数，表示给定的序列。序列中每个数字不超过 10^9。 输出说明 输出序列中逆序对的数目。 输入样例 6 5 4 2 6 3 1 输出样例 11
不难发现，对于每一个数如果我们想要暴力去遍历每一个的数的逆序对数，显然时间复杂度是O(n^2)，我们要找一个更加高效的方法。
我们不妨将目光放到归并排序上，所谓的归并排序也是排序的一种，像冒泡排序和快速排序都是我们的老朋友了，而对于归并排序，时间复杂度上和快速排序一致，不同的是它实现的过程是稳定的，下面我就这一个样例用递归方法归并排序实现以下过程：
但是这和我们要求的逆序对有什么关系呢？
不妨再仔细思考一下归并排序的过程，为了得到最后的稳定有序的序列，我们将每一部分都按区块进行了排序，最后合并，一直重复这一个过程。那逆序对的特征又是什么呢？数出现在排序后本该出现之前的位置的值，那么我们可以在归并排序的过程中统计逆序对的数量，由于归并排序的时间复杂度是O(n*log n),因此不会超时，下面给出实现代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int a[N];
int h[N];
long long ans = 0;
//模拟合并
void merge(int l, int r, int mid)
{
int pos = l;
int i = l;
int j = mid + 1;
while (i <= mid && j <= r)
{
if (a[i] > a[j])
{
h[pos++] = a[j++];
// 当出现右序列的数比左序列的还小时，代表着这时候的左序列所有数都是这个数的逆序对
ans += (mid - i + 1);
}
else
{
h[pos++] = a[i++];
}
}
while (i <= mid)
h[pos++] = a[i++];
while (j <= r)
h[pos++] = a[j++];
for (int k = l; k <= r; ++k)
{
a[k] = h[k];
}
}
//模拟分组(递归)
void f(int l, int r)
{
int mid = l + ((r - l) >> 1);
if (l == r)
return;
f(l, mid);
f(mid + 1, r);
merge(l, r, mid);
}
signed main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
f(1, n);
cout << ans;
}相信自己推演几遍代码之后读者就会发现归并排序在处理逆序对问题上的妙处。
逆序对的归并排序还有另一种的表示方式，迭代归并排序，由于一般情况迭代归并排序已经足以解决竞赛中碰见的问题，因此迭代归并排序求逆序对这里我仅仅给出代码，供大家学习参考：
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int a[N], tmp[N];
long long ans = 0;
void merge(int l, int mid, int r)
{
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r)
{
if (a[i] > a[j])
{
tmp[k++] = a[j++];
ans += (mid - i + 1);
}
else
{
tmp[k++] = a[i++];
}
}
while (i <= mid)
tmp[k++] = a[i++];
while (j <= r)
tmp[k++] = a[j++];
for (int p = l; p <= r; ++p)
a[p] = tmp[p];
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
// 自底向上归并
// len <<= 1 等价于len *= 2，只不过前者是位运算效率更高
for (int len = 1; len < n; len <<= 1)
{
for (int l = 1; l + len <= n; l += (len << 1))
{
int mid = l + len - 1;
int r = min(l + (len << 1) - 1, n);
merge(l, mid, r);
}
}
cout << ans;
return 0;
}通过迭代的方法，我们容易印证出之前我给出的归并排序的时间复杂度是O(n * log n)。
其实对于这一章标题在我的算法编程路里面的位置十分的不适合，首先是逆序对并不是一个常用的算法模板，同时归并排序又不只限于解决逆序对的问题，因此这一章可能有一些突兀，就当作一篇习题章节学习逆序对这专门的一个较为独立的题型和初步了解归并排序吧。
