新算法·混合排序

目录

众所不周知，最快$O(n \log n)$的排序算法有很多，如：
快速排序、归并排序、堆排序……
这几个排序算法也各有缺点：
快排：最坏$O(n^2)$
归排：对缓存极不友好，而且要$O(n)$额外空间
堆排：同样对缓存不友好，有时候在中等大小数组上甚至跑不过插入排序。

我们就需要将他们结合起来再用上一些优化来弥补各自的缺点。

当然，小数组的神肯定还是我们的插入排序，最快O(n)、无递归、缓存友好这3个特性几乎能在小数组称霸（恶意构造的除外啊！），C++、Python、Java小数组处理都是用的插入排序+快排/归排。

我们主要还是来讲C++：
他用的依旧是主流快排，但是他用了三数取中+三路划分，还有保底得堆排序，快排子区间长度<=16直接交给插入排序，可谓是十分得快。

Python：用了TimSort（自适应的归排）

我们可以结合一下C++和Python，给你们看一下我自己做的：

template<typename T,typename Compare>
void introsort_logic(T a[],int begin,int end,Compare cmp,int d){
    while (end-begin>15){
        int i=begin,cnt=0,is=0;
        while(i<end){ // O(n)
            int run_start=i;
            bool is_ascending=true;
            while(i<end && !cmp(a[i],a[i+1]) && !cmp(a[i+1],a[i]))i++;
            if(i<end)is_ascending=!cmp(a[i+1],a[i]);
            if(is_ascending)while(i<end && !cmp(a[i+1],a[i]))i++;
            else{
                while(i<end && !cmp(a[i],a[i+1]))i++;
                int l=run_start,r=i;is=1;
                while(l<r)swap(a[l],a[r]),l++,r--;
            }
            cnt++,i++;
        }
        if(cnt==1)return; //O(1)
        if(cnt==2){ // O(1)
            int n=end-begin+1;
            int len1=find_run(a+begin,n,0,cmp),l1=begin,r1=begin+len1-1,l2=r1+1,r2=end;
            merge_run(a,l1,r1,l2,r2,cmp);
            return;
        }
        if(d<1){ // O(n ~ n log n)
            mergesort(a,begin,end,cmp);
            return;
        }
        d--;
        int l=begin,h=end,mid=(l+h)>>1;
        if(cmp(a[mid],a[l]))swap(a[l],a[mid]);
        if(cmp(a[h],a[mid]))swap(a[mid], a[h]);
        if(cmp(a[mid],a[l]))swap(a[l],a[mid]);
        T p=a[mid];swap(a[mid],a[l]);
        int lt=l,gt=h;i=l+1;
        while(i<=gt){ // O(n)
            if(cmp(a[i],p))swap(a[i],a[lt]),lt++,i++;
            else if(cmp(p,a[i]))swap(a[i],a[gt]),gt--;
            else i++;
        }
        introsort_logic(a,begin,lt-1,cmp,d),begin=gt+1;
        if(begin>=end)return;
    }
    insertion_sort(a,begin,end,cmp);
}
template<typename T,typename Compare=less<T>>
void sort(T a[], int begin, int end, Compare cmp = Compare()) {
    if(begin>=end)return;
    if(end-begin>512&&is_integral<T>::value){
        int i=begin,cnt=0,is=0;
        while(i<end){ // O(n)
            int run_start=i;
            bool is_ascending=true;
            while(i<end && !cmp(a[i],a[i+1]) && !cmp(a[i+1],a[i]))i++;
            if(i<end)is_ascending=!cmp(a[i+1],a[i]);
            if(is_ascending)while(i<end && !cmp(a[i+1],a[i]))i++;
            else{
                while(i<end && !cmp(a[i],a[i+1]))i++;
                int l=run_start,r=i;is=1;
                while(l<r)swap(a[l],a[r]),l++,r--;
            }
            cnt++,i++;
        }
        if(cnt==1)return; //O(1)
        if(cnt==2){ // O(1)
            int n=end-begin+1;
            int len1=find_run(a+begin,n,0,cmp),l1=begin,r1=begin+len1-1,l2=r1+1,r2=end;
            merge_run(a,l1,r1,l2,r2,cmp);
            return;
        }
        radix_sort_64(a+begin,end-begin+1);
    }
    else introsort_logic(a,begin,end,cmp,(31-clz(end-begin+1))<<1);
}

最好$O(n)$，最坏$O(n \log n)$

所以，排序一定要用混合的，单一排序算法遇到恶意构造容易被拉爆，主流混合：
归排+插排、快排+堆排+插排、快排+归排。

恭喜你，学会了新算法：混合排序。
混合排序：
难度：中等
方法：将多个排序算法混合起来，来弥补各自的缺点
用处：处理恶意构造的数据，避免被拉爆

课后习题：
自己写出一个快排+其他排序 或者 归排+其他排序 的混合排序算法