归并排序(求逆序对)

https://blog.csdn.net/yuehailin/article/details/68961304

#include<bits/stdc++.h>
using namespace std;
void merge(int a[],int first,int mid,int last,int temp[])
{
	int i=first,j=mid+1;
	int m=mid,n=last;
	int k=0;
	while(i<=m&&j<=n)
	{
		if(a[i]<a[j])
		  temp[k++]=a[i++];
		else 
		  temp[k++]=a[j++];
	}
	while(i<=m)
	    temp[k++]=a[i++];
	while(j<=n)
	    temp[k++]=a[j++];
	for(i=0;i<k;i++)
	a[first+i]=temp[i];
}
void mergesort(int a[],int first,int last,int temp[])
{
	if(first<last)
	{
		int mid=(first+last)/2;
		mergesort(a,first,mid,temp);
		mergesort(a,mid+1,last,temp);
		merge(a,first,mid,last,temp);
	}
}
bool Mergesort(int a[],int n)
{
	int *p=new int[n];
	if(p==NULL)
	 return false;
	mergesort(a,0,n-1,p);
	delete[] p;
	return 1;
}
int main() 
{
	int n;
	int a[200]; 
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	Mergesort(a,n);
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	
	
	
	
	
	
	return 0;
}

求逆序对？

answer：

比如将下面两个区间排序

\qquad a_iai​ \quad mid=4mid=4 \quad a_jaj​

\quad 3\,4\,7\,93479 \qquad \qquad 1\,5\,8\,1015810

首先将右区间的 11 取出，放到r_krk​中，此时 11 是比每个a_iai​中的元素都小，也就是说此时i的指针指向a_1a1​的位置，此刻得到的逆序对的数量为 44 ； r_k= 1rk​=1 ;

然后再将a_iai​和a_jaj​比较（直到a_i<a_jai​<aj​），a_i<a_jai​<aj​ 将a_iai​的元素放到r_krk​中； r_k= 1\,3\,4rk​=134;

现在a_j>a_iaj​>ai​, ii 指向a_3a3​的位置，将 55 放到r_krk​中，得到的逆序对数量为 22 ； r_k= 1\,3\,4\,5rk​=1345

以此类推，直到进行完归并排序，每次合并都会求出逆序对的数目，即mid-i+1mid−i+1,最后每次将ansans加上mid-i+1mid−i+1即可得到最后的答案；

#include<bits/stdc++.h>
using namespace std;
const int maxn=1008611;
int a[maxn],temp[maxn];
int n;
long long ans=0;
void msort(int l,int r)
{
	if(l==r)  return ;
	
	int mid=(l+r)/2;
	int m=mid,n=r;
	msort(l,mid);
	msort(mid+1,r);
	int i=l,j=mid+1,k=0;
	while(i<=m&&j<=n)
	{
		if(a[i]<a[j]) 
		temp[k++]=a[i++];
		else {
			temp[k++]=a[j++];
			ans+=mid-i+1;
		}
	  }
	while(i<=m) temp[k++]=a[i++];
	while(j<=n) temp[k++]=a[j++];
	for(i=0;i<k;i++)
	{
		a[l+i]=temp[i];
	} 
	 
	  
	
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	msort(0,n-1);
	printf("%lld\n",ans);
	
	
	
	
	return 0;
}