排序

一、快排 \(quick sort\)

#include<bits/stdc++.h>
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)
        {
            i++;
        }
        while(a[j]>mid)
        {
            j--;
        }
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++,j--;
        }
        if(l<j)
        {
            kp(l,j);
        }
        if(i<r)
        {
            kp(i,r);
        }
    }
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	kp(1,n);
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<" ";
	}
    return 0;
}

二、归并\(mergersort\)

#include<bits/stdc++.h>
#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<<a[i]<<" ";
	} 
}