归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

图示：

模板

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=500000+10;
	int n,a[N],b[N];
	void Sort(int l,int r)
	{
		if(l>=r) return;
		int mid=(l+r)/2;
		int p1=l,p2=mid+1,pos=l;
		Sort(l,mid);Sort(mid+1,r);
		while(p1<=mid&&p2<=r)
		{
			if(a[p1]<=a[p2]) b[pos++]=a[p1++];
			else b[pos++]=a[p2++]; 
		}
		while(p1<=mid) b[pos++]=a[p1++];
		while(p2<=r) b[pos++]=a[p2++];
		for(int i=l;i<=r;i++) a[i]=b[i];
	}
    void yzmain()
    {
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",a+i);
    	Sort(1,n);
    	for(int i=1;i<=n;i++) printf("%d ",a[i]);
        return;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    _yz::yzmain();
    return 0;
}

求逆序对

归并排序是将数列 $[l,r]$ 分成两半 $[l,mid]$ 和 $[mid+1,r]$ 分别进行归并排序，然后再将这两半合并起来。

在合并的过程中（设 $l\le i\le mid$ ， $mid+1\le j\le r$ ），当 $a_i\le a_j$ 时，并不产生逆序数；当 $a_i> a_j$ 时，在前半部分中比 $a_i$ 大的数都比 $a_j$ 大，将 $a_j$ 放在 $a_i$ 前面的话，逆序数要加上 $mid-i+1$ 。因此，可以在归并排序中的合并过程中计算逆序数。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=500000+10;
	int n,a[N],b[N];
	long long ans=0;
	void Sort(int l,int r)
	{
		if(l>=r) return;
		int mid=(l+r)/2;
		int p1=l,p2=mid+1,pos=l;
		Sort(l,mid);Sort(mid+1,r);
		while(p1<=mid&&p2<=r)
		{
			if(a[p1]<=a[p2]) b[pos++]=a[p1++];
			else b[pos++]=a[p2++],ans+=mid-p1+1; 
		}
		while(p1<=mid) b[pos++]=a[p1++];
		while(p2<=r) b[pos++]=a[p2++];
		for(int i=l;i<=r;i++) a[i]=b[i];
	}
    void yzmain()
    {
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",a+i);
    	Sort(1,n);
    	printf("%lld\n",ans);
        return;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    _yz::yzmain();
    return 0;
}

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/9d13b6ee3755/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 逆序对排序分治

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158