逆序对——归并排序
逆序对：满足a[i]>a[j]且i<j这两个条件
25级校队训练赛502 - Virtual Judge![]()
https://vjudge.net/contest/808881#problem/D
题目描述：现有n个数组成了一个序列，求这段正整数序列中逆序对的数目并输出
解题思路：采用归并排序的方法进行计算
代码展现：
第一种：
#include <bits/stdc++.h>
using namespace std;
int n,a[500010],c[500010];
long long ans;
void msort(int b,int e)//b为左边界，e为右边界
{
if(b==e)
return;//当左右边界相等的时候，递归结束
int mid=(b+e)/2,i=b,j=mid+1,k=b;
//mid将数据分成了左半部分和右半部分；
//i和j此时为左右两部分开始的值，k是临时数组c的索引下标，
//k专门标记要把元素写到临时数组c的那一个位置 ，用于合并两个有序子数组
msort(b,mid),msort(mid+1,e);//保证左右区间都是严格升序的有序数组
while(i<=mid&&j<=e)//i不能超过左半部分的最右边，j不能超过右边界
{
if(a[i]<=a[j])
c[k++]=a[i++];
//左元素小于右元素：
//把a[i]写到临时数组的k位置
else{
c[k++]=a[j++];
//左元素大于右元素，此时满足a[i]>a[j]&&i<j这个条件
//把a[j]写到临时数组的k位置
ans+=mid-i+1;
//逆序对数量=左区间剩余未遍历的元素个数=mid-i+1
}
}
while(i<=mid)
c[k++]=a[i++];//合并循环结束后，把元素写入c数组中，不产生多余的逆序对
while(j<=e)
c[k++]=a[j++];//合并循环结束后，把元素写入c数组中，不产生多余的逆序对
for(int l=b;l<=e;l++)
a[l]=c[l];//把存入临时数组c中的数据拷贝回a数组中，更新值
}int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
msort(1,n);
cout<<ans;
return 0;
}
第二种：
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
int a[N], tmp[N];
long long ans = 0;
void merge(int l, int r){
if(l >= r) return;
int mid = (l + r) /2;
merge(l, mid);
merge(mid + 1, r);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r)
{
if(a[i] <= a[j]){
tmp[k++] = a[i++]; }
else
{ tmp[k++] = a[j++];
ans += mid - i + 1; }
}
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() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
merge(1, n);
cout << ans << endl;
return 0;
}
两种代码中的核心算法始终为：
void msort(int b,int e)//b为左边界，e为右边界
{
if(b==e)
return;//当左右边界相等的时候，递归结束
int mid=(b+e)/2,i=b,j=mid+1,k=b;
//mid将数据分成了左半部分和右半部分；
//i和j此时为左右两部分开始的值，k是临时数组c的索引下标，
//k专门标记要把元素写到临时数组c的那一个位置 ，用于合并两个有序子数组
msort(b,mid),msort(mid+1,e);//保证左右区间都是严格升序的有序数组
while(i<=mid&&j<=e)//i不能超过左半部分的最右边，j不能超过右边界
{
if(a[i]<=a[j])
c[k++]=a[i++];
//左元素小于右元素：
//把a[i]写到临时数组的k位置
else{
c[k++]=a[j++];
//左元素大于右元素，此时满足a[i]>a[j]&&i<j这个条件
//把a[j]写到临时数组的k位置
ans+=mid-i+1;
//逆序对数量=左区间剩余未遍历的元素个数=mid-i+1
}
}
while(i<=mid)
c[k++]=a[i++];//合并循环结束后，把元素写入c数组中，不产生多余的逆序对
while(j<=e)
c[k++]=a[j++];//合并循环结束后，把元素写入c数组中，不产生多余的逆序对
for(int l=b;l<=e;l++)
a[l]=c[l];//把存入临时数组c中的数据拷贝回a数组中，更新值
}