快排&归并模板

thomas_zjl · 2020-09-19 21:43:47 · 个人记录

给自己看的

归并：

#include<bits/stdc++.h>
using namespace std;
int a[100001],b[100001],n;
void msort(int l,int r)
{
    if(l==r)
    {
        return;
    }
    int i,j,m=(l+r)>>1,u=l;
    msort(l,m);
    msort(m+1,r);
    i=l,j=m+1;
    while(i<=m&&j<=r)
    {
        if(a[i]<a[j])
        {
            b[u++]=a[i++];
        }
        else
        {
            b[u++]=a[j++];
        }
    }
    while(i<=m)
    {
        b[u++]=a[i++];
    }
    while(j<=r)
    {
        b[u++]=a[j++];
    }
    for(i=l;i<=r;i++)
    {
        a[i]=b[i];
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    msort(1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

快排：

#include<bits/stdc++.h>
using namespace std;
int a[100001],n;
void kp(int l,int r)
{
    int t;
    int i=l;
    int j=r;
    int mid=a[(l+r)/2];
    while(i<=j)
    {
        while((i<=j)&&(mid>a[i]))
        {
            i++;
        }
        while((i<=j)&&(mid<a[j]))
        {
            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()
{
    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]<<" ";
    }
    cout<<endl;
    return 0;
}