1.声明:笔者所有代码都是手打的,没有任何的抄袭

2.时间复杂度接近 $O(nlogn)$ ,但是常数比较大,空间占用比较大

3.评测可以去快排这道题测试

1. trie树排序(代码已经被我整的不像一个trie了)

#include <bits/stdc++.h>
using namespace std ;
int idx ;
int *tr,*id ;
void calc(int u,int v)
{
    while(id[u]--) printf("%d ",v) ;
    if(tr[u<<1]) calc(tr[u<<1],v<<1) ;
    if(tr[u<<1|1]) calc(tr[u<<1|1],v<<1|1) ;
}
int main()
{
    int n ;
    scanf("%d",&n) ;
    tr=new int[n<<5] ;
    id=new int[n<<5] ;
    while(n--)
    {
        int x ;
        scanf("%d",&x) ;
        int j=0 ;
        for(register int i=31;~i;i--)
        {
            if(!tr[j<<1|x>>i&1]) tr[j<<1|x>>i&1]=++idx 
            // 这一位为0则到j<<1（也就是2*j），为1则到j<<1|1（也就是2*j+1）
            // 摒弃了trie树的下标方式，借鉴了线段树/堆的下标方式
            j=tr[j<<1|x>>i&1] ;
        }
        id[j]++ ;
    }
    calc(0,0) ;   //打印
    delete[] tr ;
    delete[] id ;
    return 0 ;
}

注:开动态数组,节省空间

2. 最长连续上升子序列归并排序

(深搜+vector传参)

#include <bits/stdc++.h>
using namespace std ;
typedef vector<int> vint ;
const int N=100001 ;
int arr[N] ;
vint ans ;
vector<vint> sub ;
int n ;
void init()
{
    int last=-1 ;
    for(int i=1;i<=n;i++)
    {
        int a=arr[i] ;
        if(last==-1) last=a,sub.push_back({a}) ;
        else if(last>a) sub.push_back({a}) ;
        else last=a,sub[sub.size()-1].push_back(a) ;
    }
}
vint merge(int l,int r)
{
    if(l>r) return {} ;
    if(l==r) return sub[l] ;
    int mid=l+r>>1 ;
    vint ll=merge(l,mid) ;
    vint rr=merge(mid+1,r) ;
    vint res ;
    int i=0,j=0 ;
    while(i<ll.size()&&j<rr.size())
        if(ll[i]<rr[j]) res.push_back(ll[i++]) ;
        else res.push_back(rr[j++]) ;
    while(i<ll.size()) res.push_back(ll[i++]) ;
    while(j<rr.size()) res.push_back(rr[j++]) ;
    return res ;
}
int main()
{
    scanf("%d",&n) ;
    for(int i=1;i<=n;i++)   
        scanf("%d",&arr[i]) ;
    init() ;
    ans=merge(0,sub.size()-1) ;
    for(auto i:ans) printf("%d ",i) ;
    return 0 ;
}

3. 超快速排序

我写这段代码的故事其实挺有意思的,有一次我搜索快排,结果百度给我联想到了超快速排序,我搜了下发现是某个本科生浑水摸鱼写的一篇论文,结果闲的没事干的我就帮这个本科生写了一段完整代码
主要内容就看前面我给的链接吧
这个是我写的常数最小的排序了

#include <cstdio>
int q[100010] ;
int n ;
void super_qsort(int left,int right,int len)
{
    if(left>=right) return ;
    if(len<0) return ;
    int l=left,r=right ;
    while(l<=r)
    {
        while(l<=r&&q[l]>>len&1^1) l++ ;
        while(l<=r&&q[r]>>len&1) r-- ;
        if(l<=r) q[l]^=q[r],q[r]^=q[l],q[l]^=q[r] ;
    }
    super_qsort(left,l-1,len-1) ;
    super_qsort(l,right,len-1) ;
}
int log2(int k)
{
    int res=0 ;
    for(int i=k;i;i>>=1) res++ ;
    return res ;
}
int read()
{
    char ch=getchar() ; int a=0 ;
    while(ch>'9'||ch<'0') ch=getchar() ;
    while(ch>='0'&&ch<='9') a=(a<<1)+(a<<3)+(ch&15),ch=getchar() ;
    return a ;
}
int main()
{
    n=read() ;
    int maxv=0 ;
    for(int i=1;i<=n;i++)
    {
        q[i]=read() ;
        if(maxv<q[i]) maxv=q[i] ;
    }
    int len=log2(maxv) ;
    super_qsort(1,n,len) ;
    for(int i=1;i<=n;i++) 
        printf("%d ",q[i]) ;
    return 0 ;
}

-----2020-10-22更新------
离 $csp$ 第二轮只有一天了，共勉！
线段树排序（又称锦标赛排序）
很简单的线段树，支持单点修改，区间（而且是整个区间）查询，别的就没了
修改方面的常数比较大

#include <cstdio>
const int N=400010 ;
struct node { int l,r,val,pos; } tr[N] ;
int a[N] ;
void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,a[l],l} ;
    else
    {
        tr[u]={l,r} ;
        int mid=l+r>>1 ;
        build(u<<1,l,mid) ;
        build(u<<1|1,mid+1,r) ;
        if(tr[u<<1].val<tr[u<<1|1].val) tr[u].val=tr[u<<1].val,tr[u].pos=tr[u<<1].pos ;
        else tr[u].val=tr[u<<1|1].val,tr[u].pos=tr[u<<1|1].pos ;
    }
}
void modify(int u,int x)
{
    if(tr[u].l==tr[u].r) tr[u].val=1<<30 ;
    else
    {
        int mid=tr[u].l+tr[u].r>>1 ;
        if(mid<x) modify(u<<1|1,x) ;
        else modify(u<<1,x) ;
        if(tr[u<<1].val<tr[u<<1|1].val) tr[u].val=tr[u<<1].val,tr[u].pos=tr[u<<1].pos ;
        else tr[u].val=tr[u<<1|1].val,tr[u].pos=tr[u<<1|1].pos ;
    }
}
int main()
{
    int n ;
    scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    build(1,1,n) ;
    for(int i=1;i<=n;i++)
    {
        printf("%d ",tr[1].val) ;
        modify(1,tr[1].pos) ;
    }
    return 0 ;
}