归并求逆序对【模板】

代码：

#include <stdio.h>

const int M=999999;

int A[500];
int cunt=0;
int L[250],R[250];

void Merge(int Left,int Middle,int Right)
{
	int n1=Middle-Left+1;
	int n2=Right-Middle;

	for(int i=1;i<=n1;i++)
		L[i]=A[Left+i-1];
	for(i=1;i<=n2;i++)
		R[i]=A[Middle+i];

	L[n1+1]=M;
	R[n2+1]=M;

	i=1;
	int j=1;
	for(int k=Left;k<=Right;k++)
	{
		if(L[i]<=R[j])
			A[k]=L[i++];

		else
		{
			A[k]=R[j++];
			cunt+=n1-i+1;                 //cunt为全局变量
		}
	}
}

void Merge_sort(int Left,int Right)
{
	int Middle;
	if(Left<Right)
	{
		Middle=(Left+Right)/2;
		Merge_sort(Left,Middle);                      // 二分分解左部分
		Merge_sort(Middle+1,Right);                // 二分分解有部分
		Merge(Left,Middle,Right);                      //合并两部分
	}
}

int main()
{
	int n;
	scanf("%d",&n);

	int i;
	for(i=1;i<=n;i++)
		scanf("%d",&A[i]);

	Merge_sort(1,n);

	printf("%d\n",cunt);

	return 0;
}

运行结果：

5
2 3 8 6 1

5