归并排序求逆序对数

归并排序

归并排序是不断运用分治的思想，不断的将数组二分。然后将两个数组的数进行依次比较，在比较过程中依次将较小的数放在另一个新的数组中，在这个过程中如果出现前边数组的数大于后边数组的数，即出现了逆序数，统计即可。当两个数组都遍历到最后时，新的数组中的数即为有序数，然后将这个有序数组重新赋予原数组，在进行下一个分治过程即可。

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int t[1000000];
int ans=0,n;
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,p=l;
	while(i<=mid&&j<=r) 
	{
		if(a[i]<a[j])
		t[p++]=a[i++];
		else
		{
			t[p++]=a[j++];
			ans=ans+mid-i+1;//此时两边都是排好序了的，当前面的序列中有一个数大于后面的一个数时，前面序列中剩下的数都大于这个数，共mid-i+1个
		}
	}
	while(i<=mid)
	{
		t[p++]=a[i++];
	}
	while(j<=r)
	{
		t[p++]=a[j++];
	}
	for(int i=l;i<=r;i++)
	a[i]=t[i];//把有序数组t复制给数组a变成有序的，保证合并上一层有序数列时满足条件
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	merge(1,n);
	printf("%d\n",ans);
	return 0;	
}

打赏