排序
一、快排 \(quick sort\)
#include
using namespace std;
int a[10001];
void kp(int l,int r)
{
int mid=a[(l+r)/2];
int i=l,j=r;
while(i<=j)
{
while(a[i]mid)
{
j--;
}
if(i<=j)
{
swap(a[i],a[j]);
i++,j--;
}
if(l>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
kp(1,n);
for(int i=1;i<=n;i++)
{
cout<
二、归并\(mergersort\)
#include
#define N 500000
using namespace std;
int n,a[N],b[N];
long long ans=0;
void merger(int l,int mid,int r)
{
int k=l,i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(a[i]>a[j])
{
ans+=mid-i+1;
}
b[k++]=a[i]<=a[j]?a[i++]:a[j++];
}
while(i<=mid)
{
b[k++]=a[i++];
}
while(j<=r)
{
b[k++]=a[j++];
}
for(int i=l;i<=r;i++)
{
a[i]=b[i];
}
}
void mergersort(int l,int r)
{
if(l==r)
{
return ;
}
int mid=(l+r)/2;
mergersort(l,mid);
mergersort(mid+1,r);
merger(l,mid,r);
}
int main ()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
mergersort(1,n);
for(int i=1;i<=n;i++)
{
cout<