5.1归并递归排序.cpp

数据结构与算法实验题 5.1 排序

★实验任务

通过交换元素位置实现排序的算法通常称为交换排序算法。如果只允许交换相邻元素的位置，则称为相邻交换排序算法，如冒泡排序算法。

给定 n 个待排成升序的整数，求出相邻交换排序算法交换元素位置的最少次数。

★数据输入

输入第一行为一个正整数 n (n < =500000)

输入第二行为 n 个整数，这些整数可能有相同的。

★数据输出

输出相邻交换排序算法交换元素位置的最少次数。

PS:请用 long long 来计算次数,输入输出请用 scanf，printf

#include
using namespace std;
int a[500005]m[500005]n;
long long ans=0;//记录逆序对
void msort（int lint r）
{
	if（l==r） return;
	int mid=（l+r）/2;
	msort（lmid）msort（mid+1r）;
	int i=lj=mid+1k=l;
	while（i<=mid&&j<=r）
	{
		if（a[i]<=a[j]）
		{
			m[k]=a[i];
			k++;
			i++;
		}
		else if（a[i]>a[j]）
		{
			m[k]=a[j];
			k++;