排序算法代码仓库

经典排序class="superseo">算法 插入排序

#include 
#include 
#include 

using namespace std;
const int N=1e6+1000;
int n;
int a[N];

void insert_sort()
{
    for(int i=2; i<=n; i++)
    {
        if(a[i]<a[i-1])
        {
            a[0]=a[i]; // 哨兵
            int tmp=a[i];
            int j=i-1;
            while(tmp<a[j])
                a[j+1]=a[j],j--;
            a[j+1]=tmp;
        }
    }
}


int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=n; i++)cout<<a[i]<<' ';
    cout<<endl;
    insert_sort();
    for(int i=1; i<=n; i++)cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}

希尔排序

#include 
#include 
#include 

using namespace std;
const int N=1e6+1000;
int n;
int a[N];
int dir[]= {1,3,5};

void shell_insert(int k)
{
    for(int i=k; i<n; i++)
    {
        if(a[i]<a[i-k]) // 前大于后
        {
            int tmp=a[i];
            int j=i-k;
            while(j>=0&&a[j]>tmp)
                a[j+k]=a[j],j-=k;
            a[j+k]=tmp;
        }
    }
}

void shell_sort()
{
    for(int i=2;i>=0;i--)
    shell_insert(dir[i]);
}

int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    cin>>n;
    for(int i=0; i<n; i++)cin>>a[i];
    for(int i=0; i<n; i++)cout<<a[i]<<' ';
    cout<<endl;
    shell_sort();
    for(int i=0; i<n; i++)cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}

选择排序

#include 
#include 
#include 

using namespace std;
const int N=1e6+1000;
int n;
int a[N];

void select_sort()
{
    for(int i=1;i<=n;i++)
    {
        int max_loc=1;
        for(int j=1;j<=n-i+1;j++)
        {
            if(a[j]>a[max_loc])max_loc=j;
        }
        swap(a[max_loc],a[n-i+1]);
    }
}


int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=n; i++)cout<<a[i]<<' ';
    cout<<endl;
    select_sort();
    for(int i=1; i<=n; i++)cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}

堆排序

#include 
#include 
#include 

using namespace std;
const int N=1e6+1000;
int n;
int a[N];

void adjust(int s,int m)
{
    int tmp=a[s];
    for(int j=2*s; j<=m; j<<=1)
    {
        if(j<m&&a[j+1]>a[j])j++;
        if(tmp>=a[j])break;
        a[s]=a[j];
        s=j;
    }
    a[s]=tmp;
}

void build()
{
    for(int i=n/2; i>0; i--)
        adjust(i,n);
}

void heap_sort()
{
    build(); // 别忘了建堆
    for(int i=n; i>0; i--)
    {
        swap(a[1],a[i]);
        //for(int p=1; p<=n; p++)cout<
        //cout<
        adjust(1,i-1);
    }
}

int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=n; i++)cout<<a[i]<<' ';
    cout<<endl;
    heap_sort();
    for(int i=1; i<=n; i++)cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}

冒泡排序

#include 
#include 
#include 

using namespace std;
const int N=1e6+1000;
int n;
int a[N];

void bubble_sort()
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n-i-1; j++)
            if(a[j]>a[j+1])
                a[j]^=a[j+1],a[j+1]^=a[j],a[j]^=a[j+1];
    }
}

int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    cin>>n;
    for(int i=0; i<n; i++)cin>>a[i];
    for(int i=0; i<n; i++)cout<<a[i]<<' ';
    cout<<endl;
    bubble_sort();
    for(int i=0; i<n; i++)cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}

快速排序

#include 
#include 
#include 

using namespace std;
const int N=1e6+1000;
int n;
int a[N];

int part(int s,int t)
{
    int tmp=a[s]; // 枢轴元素
    int i=s,j=t;
    while(i<j)
    {
        while(i<j&&a[j]>=tmp)j--;
        a[i]=a[j];
        while(i<j&&a[i]<=tmp)i++;
        a[j]=a[i];
    }
    a[i]=tmp;
    return i;
}

void quick_sort(int s,int t)
{
    if(s>=t)return;
    int pos=part(s,t);
    quick_sort(s,pos-1);
    quick_sort(pos+1,t);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    #endif
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
    cout<<endl;
    quick_sort(0,n-1);
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}

归并排序

#include 
#include 
#include 

using namespace std;
const int N=1e6+1000;
int n;
int a[N],tmp[N];

void merge1(int l,int mid,int r)
{
    int i=l,j=mid+1,loc=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j])
        tmp[loc++]=a[i++];
        else
        tmp[loc++]=a[j++];
    }
    while(i<=mid)tmp[loc++]=a[i++];
    while(j<=r)tmp[loc++]=a[j++];

    // copy
    for(int i=l;i<=r;i++)
    a[i]=tmp[i];
}

void merge_sort(int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    merge1(l,mid,r);
}


int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=n; i++)cout<<a[i]<<' ';
    cout<<endl;
    merge_sort(1,n);
    for(int i=1; i<=n; i++)cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}