归并排序的题 只需要记录排序的次数。
递归法实现 归并排序
#include<iostream>
#include<stdio.h>
using namespace std;
int a[1000005];
long long sum;
void smerge(int x,int mid,int y)//归并
{
int i,j,k=x;
int n1=mid-x+1;
int n2=y-mid;
int left[500005];
int right[500005];
for (i=0;i<n1;i++)
{
left[i]=a[x++];
}
for (j=0;j<n2;j++)
{
right[j]=a[++mid];
}
i=j=0;
while(i<n1&&j<n2)
{
if(left[i]<=right[j])
{
a[k++]=left[i++];
}
else
{
a[k++]=right[j++];
sum+=n1-i;//记录排序的 次数
}
}
while(i<n1)
a[k++]=left[i++];
while(j<n2)
a[k++]=right[j++];
}
void ssort(int x,int y)//归并排序
{
if (x<y)
{
int mid=(x+y)/2;
ssort(x,mid);
ssort(mid+1,y);
smerge(x,mid,y);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,i;sum=0;
cin>>n;
for (i=0;i<n;i++)
scanf("%d",&a[i]);
ssort(0,n-1);
cout<<sum<<endl;
}
return 0;
}