归并排序求逆序数
思路:
在归并排序的过程中求得逆序数
回顾归并排序的思路:
1. 确定分界点
2. 左右递归
3. 归并区间
4. 将剩余元素传递到数组
在左右区间递归排序的过程中,我们已经将两个区间排序完成(升序)
所以在归并,左右两区间元素比较时,右区间的元素$a[j]<a[i]$时,会产生逆序对
$(a[i],a[j])$是逆序对,那么$(a[i+1],a[j])$也是逆序对,共有$mid-i+1$个逆序对
key code:
if (a[i] <= a[j]) temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
res += x - i + 1;
}
值得注意的是res+=x-i+1
,不要写成res=x-i+1
思考:为什么采用归并排序求逆序数呢?(相比于直接求逆序数,归并排序有什么优点呢)
归并的本质是分治的思想。同时在求逆序数时,相比于在无序数组中两个数字两个数字直接求时,如果将分治得到的有序数组中的元素比较一次,便能得到多个逆序数,会大大减少开销。
代码:
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], temp[N] ;
typedef long long LL;
LL merge_sort(int a[], int l, int r)
{
if (l >= r) return 0;
int x = l + r >> 1;
LL res = 0;
res=merge_sort(a, l, x)+merge_sort(a, x + 1, r);
int i = l, j = x + 1, k = 0;
while (i <= x && j <= r)
if (a[i] <= a[j]) temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
res += x - i + 1;
}
while (i <= x) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (int i = l, k = 0; i <= r; i++, k++) a[i] = temp[k];
return res;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
cout << merge_sort(a, 0, n - 1);
return 0;
}