直接插入排序

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
void insert_sort()
{
    for(int i=1;i<n;i++)
    {
        int q=a[i],j=i;
        while(j&&a[j-1]>q)
            a[j]=a[j-1],j--;
        a[j]=q;
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    insert_sort();
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}

折半插入排序

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
void binary_search_insert_sort()
{
    for(int i=1;i<n;i++)
    {
        if(a[i]>=a[i-1])continue;//因为这一步使下面变成左闭右开区间
        int q=a[i];
        int l=0,r=i-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(a[mid]>q)
                r=mid;
            else
                l=mid+1;
        }
        for(int j=i-1;j>=r;j--)
            a[j+1]=a[j];
        a[r]=q;
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    binary_search_insert_sort();
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}

冒泡排序

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
void bubble_sort()
{
   for(int i=0;i<n-1;i++)
   {
       bool has_swap=false;
       for(int j=n-1;j>i;j--)
       {
           if(a[j-1]>a[j])
           {
               swap(a[j-1],a[j]);
               has_swap=true;
           }
       }
       if(!has_swap)return;
   }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    bubble_sort();
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}

简单选择排序

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
void select_sort()
{
   for(int i=0;i<n-1;i++)
   {
       int k=i;
       for(int j=i+1;j<n;j++)
            if(a[j]<a[k])
                k=j;
        swap(a[i],a[k]);
   }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    select_sort();
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}

希尔排序

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
void shell_sort()
{
   for(int d=n/2;d;d/=2)
   {
       for(int start=0;start<d;start++)
       {
           for(int i=start+d;i<n;i+=d)
           {
                int j=i,q=a[i];
                while(j>start&&a[j-d]>q)
                    a[j]=a[j-d],j-=d;
                a[j]=q;
           }
       }
   }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    shell_sort();
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}

快速排序

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
void quick_sort(int l,int r)
{
   if(l>=r)return;
   int i=l-1,j=r+1,x=a[l+r>>1];
   while(i<j)
   {
       do i++;while(a[i]<x);
       do j--;while(a[j]>x);
       if(i<j)swap(a[i],a[j]);
   }
   quick_sort(l,j);
   quick_sort(j+1,r);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    quick_sort(0,n-1);
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}

堆排序(大根堆,数组下标从1开始)

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n,sz;
void down(int u)
{
    int t=u;
    if(2*u<=sz&&a[2*u]>a[t])t=2*u;
    if(2*u+1<=sz&&a[2*u+1]>a[t])t=2*u+1;
    if(t!=u)
    {
        swap(a[t],a[u]);
        down(t);
    }
}
void heap_sort()
{
    sz=n;
    for(int i=n/2;i;i--)
        down(i);
    for(int i=0;i<n-1;i++)
    {
        swap(a[1],a[sz]);
        sz--;
        down(1);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    heap_sort();
    for(int i=1;i<=n;i++)
        cout<<a[i]<<' ';
    return 0;
}

归并排序

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],w[N];
int n,sz;
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);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j])w[k++]=a[i++];
        else w[k++]=a[j++];
    }
    while(i<=mid)
        w[k++]=a[i++];
    while(j<=r)
        w[k++]=a[j++];
    for(int i=l,j=0;j<k;j++,i++)
        a[i]=w[j];
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    merge_sort(0,n-1);
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}

桶排序

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],s[N],w[N];
int n;
void bucket_sort()
{
    for(int i=0;i<n;i++)s[a[i]]++;
    for(int i=1;i<N;i++)s[i]+=s[i-1];
    for(int i=n-1;i>=0;i--)w[--s[a[i]]]=a[i];
    for(int i=0;i<n;i++)a[i]=w[i];
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    bucket_sort();
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}