求解逆序对数的几种方法

大家好，欢迎来到IT知识分享网。

求解逆序对数的几种方法：

设A为一个包含n个数字的有序集合$(n>1)$，其中所有的数字均不相同。
如果存在两个正整数i，j，使得$1≤i<j≤n$，且$A[i]>A[j]$，则$(A[i], A[j])$这个有序对称为A的一个逆序对。例如，数组$(3，1，4，5，2)$的逆序对有$(3,1),(3,2),(4,2),(5,2)$，共4个。

1. 两重循环来求解，时间复杂度为$O(n^2)$，大致代码如下：

int GetReverse(int* a, int n) { int sum = 0; for (int i = 0; i < n-1; ++i) { for (int j = i+1; j < n; ++j) { if (a[i] > a[j]) ++sum; } } return sum; }

2. 树状数组求解，时间复杂度$O(nlogn)$

大致思想：
假设我们有个标记数组flag，长度为n；
先在n个数中找到最大的元素e1，其下表为p1，将flag[p1]置为1，统计p1之前的1的个数，即为与e1构成的逆序对数；
找到第二大元素e2，其下标为p2，将flag[p2]置为1，统计p2之前的1的个数，即为与e2构成的逆序对数；
以此类推，全部找完之后，统计的总个数即为序列中逆序对的总数。

拿开头的例子来说：
3 1 4 5 2，初始状态flag数组均为0（约定下标从1开始）；
取最大数5，flag数组变为 0 0 0 1 0，统计下标4之前的1的个数为0，总逆序对数为0；
取第二大数4，flag数组变为 0 0 1 1 0，统计下标3之前的1的个数为0，总逆序对数为0；
取第三大数3， flag数组变为 1 0 1 1 0，统计下标1之前的1的个数为0，总逆序对数为0；
取2，flag数组变为 1 0 1 1 1，统计下标5之前的1的个数为3，总逆序对数为3；
取1，flag数组变为 1 1 1 1 1，统计下标2之前的1的个数为1，总逆序对数为4；
结束。

示例代码如下：

// 数据输入 for (int i = 1; i <= n; ++i) { scanf("%d", &num[i].val); num[i].id = i; } // 降序排列 sort(num+1, num+1+n, cmp); // 找到第k大数，统计它的下标之前总共1的个数，加到ans当中，最终输出ans即为结果 // 标记第k大数的位置，并向上更新树状数组，两个操作顺序不能颠倒 for (int i = 1; i <= n; ++i) { ans += GetSum(num[i].id); Update(num[i].id); }

3归并排序求解：

未完待续……