归并排序求逆序数

什么是逆序对

逆序对就是在一个序列中，存在i<j,a[i]>a[j]这样的一对数即是逆序对，逆序对的个数就叫逆序数。

归并排序求逆序对思路

在我们进行归并排序的过程中，我们在合并是使用双指针扫描两个有序的待合并数组，当我们在左边数组中扫到第一个大于右边数组的位置，则它后面的所有数都应该大于右边的数。我们用一个变量记录，则res=mid-i+1。

归并排序代码

using namespace std;
const int N=1e6+10;
int arr[N];
int tmp[N];
typedef long long LL;
LL ans;
LL reverse_pair(int l,int r){
	if(l>=r) return 0;
	int mid=l+r>>1;
	reverse_pair(l,mid);
	reverse_pair(mid+1,r);
	int i=l,j=mid+1,k=0;
	while(i<=mid&&j<=r){
		if(arr[i]>arr[j]){
			tmp[k++]=arr[j++];
			ans+=mid-i+1;	
		}else tmp[k++]=arr[i++];
	}
	while(i<=mid) tmp[k++]=arr[i++];
	while(j<=r) tmp[k++]=arr[j++];
	for(int i=l,j=0;i<=r;i++,j++) arr[i]=tmp[j];
	return ans;
}  
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	cout<<reverse_pair(0,n-1);
	return 0;
	
}

最后

归并排序求逆序对时需要注意，所求结果会不会爆int,如何会则需要开long long,归并排序求逆序数的时间复杂度为O(nlogn)。

逆序对

原文：https://www.cnblogs.com/zzjjblogs/p/14618948.html