1.题目
给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。
输入格式
第一行包含整数n,表示数列的长度。
第二行包含 n 个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
1≤n≤100000
输入样例:
6
2 3 4 5 6 1
输出样例:
5
2.思路
归并排序是稳定的排序,相等的元索的顺序不会改变,进而用其可以解决逆序对的问题。首先我们了解一下什么是逆序对。
逆序对:设 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个。
所谓逆序对的问题,即对给定的数组序列,求其逆序对的数量。
从逆序对定义上分析,逆序对就是数列中任意两个数满足大的在前,小的在后的组合。如果将这些逆序对都调整成顺序(小的在前,大的在后),那么整个数列就变得有序,即排序。因面,容易想到冒泡排序的机制正好是利用消除逆序来实现排序的,也就是说,交换相邻两个逆序数,最终实现整个序列有序,那么交换的次数即为逆序对的数量。
冒泡排序可以解决逆序对问题,但是由于冒泡排序本身效率不高,时间复杂度为O(n^2),对于n比较大的情况就没用武之地了。我们可以这样认为,冒泡排序求逆序对效率之所以低,是因为其在统计逆序对数量的时候是一对一对统计的,而对于范围为n的序列,逆序对数量最大可以是(n+1)*n/2,因此其效率太低.那怎样可以一下子统计多个,而不是一个一个累加呢?这个时候,归并排序就可以帮我们来解决这个问题。
在合并操作中,我们假设左右两个区间元素为:
左边:{3 4 7 9} 右边:{1 5 8 10}
那么合并操作的第一步就是比较3和1,然后将1取出来放到辅助数组中,这个时候我们发现,右边的区间如果是当前比较的较小值,那么其会与左边剩余的数字产生逆序关系,也就是说1和3、4、7、9都产生了逆序关系,我们可以一下子统计出有4对逆序对。接下来3,4取下来放到辅助数组后,5与左边剩下的7、9产生了逆序关系,我们可以统计出2对。依此类推,8与9产生1对,那么总共有4+2+1对。这样统计的效率就会大大提高,便可较好地解决逆序对问题。
而在算法的实现中,我们只需略微修改原有归并排序,当右边序列的元素为较小值时,就统计其产生的逆序对数量,即可完成逆序对的统计。.
(2).代码
const int maxn = 1e5 + 10;
int q[maxn], tmp[maxn];
void merge_sort(int q[], int l, int r)
{
if (l >= r) return; //如果只有一个数字或没有数字,则无需排序
int mid = (l + r )/2;
merge_sort(q, l, mid); //分解左序列
merge_sort(q, mid + 1, r); //分解右序列
int k = l, i = l, j = mid + 1;
while (i <= mid && j <= r) //合并
{
if (q[i] <= q[j]) tmp[k++] = q[i++];
else
{
tmp[k++] = q[j++];
ans += mid - i + 1; //统计产生逆序对的数量
}
}
while (i <= mid) tmp[k++] = q[i++]; //复制左边子序列剩余
while (j <= r) tmp[k++] = q[j++]; //复制右边子序列剩余
for (int i = l; i <= r; i++) q[i] = tmp[i];
}
其中,ans+=mid-i+1 这句代码统计新增逆序对的数量,ans作为全局变量,用于统计逆序对的数量,此时ans要增加左边剩余元素的个数。当归并排序结束后,逆序对也得到解决,ans即为逆序对的数量。
3.代码
//归并排序模板
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1e6 + 10;
int q[maxn], tmp[maxn];
long long ans = 0;
void merge_sort(int q[], int l, int r)
{
if (l >= r) return; //如果只有一个数字或没有数字,则无需排序
int mid = (l + r ) /2;
merge_sort(q, l, mid); //分解左序列
merge_sort(q, mid + 1, r); //分解右序列
int k = l, i = l, j = mid + 1;
while (i <= mid && j <= r) //合并
{
if (q[i] <= q[j]) tmp[k++] = q[i++];
else
{
tmp[k++] = q[j++];
ans += mid - i + 1;
}
}
while (i <= mid) tmp[k++] = q[i++]; //复制左边子序列剩余
while (j <= r) tmp[k++] = q[j++]; //复制右边子序列剩余
for (int i = l; i <= r; i++) q[i] = tmp[i];
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> q[i];
}
merge_sort(q, 0, n - 1);
cout << ans << endl;
return 0;
}
ans += mid - i + 1; 问一下 为什么这个地方要+1