0.目录

1.前言

2.插入排序与平衡树

3.桶排序与哈希表

4.冒泡排序与快速排序

5.分治思想

6.归并排序与CDQ分治

7.堆排序与可并堆

1.前言

在阅读之前，希望你能阅读这段话。

首先作者水平有限，错误的地方希望大家能指出我的错误。

我在最近学习了一些高级数据结构，发现一些结构和排序有诸多练习。

于是我写了这个笔记，供我自己记录，如果能帮到大家那我当然是希望的。

2.插入排序与平衡树

插入排序的思想是维护一堆数，找到不在这堆数里的数，然后加入进去，加入到比他正好比他大的节点的前面。

void InsertSort(int *a,int n){
    for(int i=1;i<=n;i++){
        int v=a[i+1];
        int j=i+1;
        for(;j&&v<a[j-1];j--)a[j]=a[j-1];
        a[j]=v;
    }
}

当然，朴素的插入排序时间复杂度为 $O(n^2)O(n2) ，不优秀。$

于是我们考虑优化。

发现插入的过程中可以前面处理的数组是有序的，于是我们珂以尝试二分优化。

void BinaryInsertSort(int *a,int n){
    for(int i=1;i<=n;i++){
        int l=1,r=i-1,idx=i;
        int tmp=a[i];
        if(a[1]<tmp&&a[i-1]>tmp){
            while(l<r){
                int mid=(l+r)/2;
                if(a[mid]>tmp)r=mid;
                else l=mid+1;
            }
            idx=l;
        }
        if(a[1]>=tmp)idx=1;
        if(a[i-1]<=tmp)idx=1;
        for(int j=i-1;j>=idx;j--)a[j+1]=a[j];
        a[idx]=tmp;
    }
}

考虑到有平移操作，因此最坏的时间复杂度仍然为 $O(n^2)O(n2) 我们要有一个能有动态插入，动态寻找后继的数据结构，由此引出了——平衡树。$

struct fhq_treap{
    int val[N],rnd[N],size[N],ch[N][2],root,tot;
    #define lc ch[x][0]
    #define rc ch[x][1]
    int update(int x){size[x]=size[lc]+size[rc]+1;return x;}
    int combine(int x,int y){
        if(!x||!y)return x+y;
        if(rnd[x]<rnd[y]){rc=combine(rc,y);return update(x);}
        else{ch[y][0]=combine(x,ch[y][0]);return update(y);}
    }
    void split(int p,int v,int &x,int &y){
        if(!p)return (void)(x=y=0);
        if(val[p]<=v)x=p,split(rc,v,ch[p][1],y);
        else split(ch[y=p][0],v,x,ch[p][0]); 
        update(p);
    }
    int rnk(int x,int k){
        while(1){
            if(k==size[lc]+1)return x;
            if(k<=size[lc])x=lc;
            else k-=size[lc]+1,x=rc;
        }
    }
    int newnode(int v){size[++tot]=1,val[tot]=v,rnd[tot]=rand();return tot;}
    void insert(int v){
        int x,y;
        split(root,v,x,y);
        root=combine(combine(x,newnode(v)),y);
    }
    void del(int v){
        int x,y,z;
        split(root,v,y,z);
        split(y,v-1,y,x);
        root=combine(combine(y,combine(lc,rc)),z);
    }
    int kth(int k){return val[rnk(root,k)];}
}st;
void BalancedTreeSort(int *a,int n){
    for(int i=1;i<=n;i++)st.insert(a[i]);
    int b[N]={0};
    for(int i=1;i<=n;i++){
        b[i]=st.kth(1);
        st.del(b[i]);
    }
    for(int i=1;i<=n;i++)a[i]=b[i];
}

这里只对平衡树做一个介绍，如果想详细学习平衡树，请点击以下链接：

平衡树家族

3.桶排序与哈希表

桶排序在这里只介绍计数排序，其他类型的桶排序略过（我不会doge）。

计数排序，相当于在每个数字的地方开一个桶。

void CountSort(int *a,int n){
    int b[N]={0},tot,cnt[N]={0},maxn=0,minn=2147483647;
    for(int i=1;i<=n;i++)maxn=max(maxn,a[i]),minn=min(minn,a[i]),++cnt[a[i]];
    for(int i=maxn;i>=minn;i--){
        while(cnt[i])b[++tot]=i,cnt[i]--;
    }
    for(int i=1;i<=n;i++)a[i]=b[i];
}

如果出现负数怎么处理呢？我会！整体加上最大值不就行了？

那么数据范围极大呢？我会！离散化，离散化不就变成 $O(n\log n)O(nlogn) 了吗？$

利用哈希表作为桶，进行排序，复杂度期望为

struct hash_table{
    int val[N],key[N],m=50021;
    void clear(){memset(key,0,sizeof(key));memset(val,0,sizeof(val));}
    int hs(int x){return (x%m+m)%m;}
    long long& operator[](int p){
        int x=hs(p);
        int t=x;
        while(key[t]!=0&&key[t]!=x)if(++t==m)t=0;
        key[t]=x;
        return val[t];
    }
}cnt;
void HashSort(int *a,int n){
    int b[N]={0},tot,maxn=0,minn=2147483647;
    for(int i=1;i<=n;i++)maxn=max(maxn,a[i]),minn=min(minn,a[i]),++cnt[a[i]];
    for(int i=maxn;i>=minn;i--){
        while(cnt[i])b[++tot]=i,cnt[i]--;
    }
    for(int i=1;i<=n;i++)a[i]=b[i];
}

实际上哈希排序没有实际意义，这里也只是通过桶排序引出哈希表这一数据结构。

4.冒泡排序与快速排序

冒泡排序是最基础的排序，复杂度为 $O(n^2)O(n2) ：$

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

如何优化到 $O(n\log n)O(nlogn) 呢？我们要用到分治思想：$

咕咕咕