归并排序c++?
发布网友
发布时间：2022-06-28 16:32
共2个回答
热心网友
时间：2023-10-09 22:36
using namespace std;
long long n,ai[1000010],t[1000005],ans;
void Merge(long long arr[], long long l,long long r)
{
if (l==r) return;
long long mid=(l+r)>>1;
Merge(arr,l,mid);
Merge(arr,mid+1,r);
long long i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if (arr[i]>arr[j])
{
t[k++]=arr[j++];
// ans+=mid-i+1;
}
else
t[k++]=arr[i++];
}
while(i<=mid) t[k++]=arr[i++];
while(j<=r) t[k++]=arr[j++];
for(i=l;i<=r;i++)
arr[i]=t[i];
}
int main()
{
cin>>n;
for(long long i=1;i<=n;i++)
cin>>ai[i];
Merge(ai,1,n);
for(int i=1;i<=n;i++)
cout<<ai[i]<<" ";
cout<<endl;
//cout<<ans<<endl;
return 0;
}
补充：
ans是求逆序对的，这里不需要
如果空间超限把long long 改成int
热心网友
时间：2023-10-09 22:36
oj代码c++如下:
#include<iostream>
using namespace std;
int a[1000016];
void merge(int l,int r,int mid)
{
int aux[r-l+1],i,j,k;
for(k=l;k<=r;k++)
aux[k-l]=a[k];
i=l;
j=mid+1;
for(k=l;k<=r;k++)
{
if(i>mid)
{
a[k]=aux[j-l];
j++;
}
else if(j>r)
{
a[k]=aux[i-l];
i++;
}
else if(aux[i-l]>aux[j-l])
{
a[k]=aux[j-l];
j++;
}
else
{
a[k]=aux[i-l];
i++;
}
}
}
void merge_sort(int l,int r)
{
if(l>=r) return ;
int mid=(l+r)/2;
merge_sort(l,mid);
merge_sort(mid+1,r);
merge(l,r,mid);
}
void mergesort(int l,int r)
{
merge_sort(l,r-1);
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(0,n);
for(i=0;i<n-1;i++)
{
printf("%d ",a[i]);
}
if(n) printf("%d\n",a[i]);//printf("%d",a[i]);
return 0;
}
