冷门科技：01-trie排序

like_tis · 2023-12-30 17:03:30 · 算法·理论

基于01-trie的排序方法

01-trie 是一种特殊的字典树，请先了解普通字典树的使用方法。

P1177题解区竟然没有01-trie这么好写的排序?

1. 01-trie简介

对于一些数字，我们把它们二进制分解。

以P1177的样例为例，4,2,4,5,1 分解后为:

将这些二进制数字当成字符串加入字典树，如图。

代码实现:

void insert(int val){
    int u=0;//根节点
    for(int i=(1<<29);i;i>>=1){//从高位拆分
        int a=bool(i&val);
        if(trie[u][a]==0) trie[u][a]=++tot;//如果没有这个节点，就新建。
        u=trie[u][a];//跳到子节点
    }
    num[u]++;//标记这个数
}

2. 用01-trie排序

容易发现，若用 0 表示左节点，1 表示右节点，则左边的数字一定比右边的数字小。

左边的节点当前这一位是0,后面更小的位再大,也不可能比当前这一位是1的大了。

所以可以对字典树进行遍历，每次先遍历 0，再遍历 1 就可以保证遍历的数字单调递增!也就实现了排序的目的!

代码实现如下：

void dfs(int u,int val,int dep){//u表示节点编号,val表示累积的数字,dep表示二进制是第几位
    if(dep==0){//到达叶节点，输出
        for(int i=1;i<=num[u];i++) printf("%d ",val);
    }
    if(trie[u][0]) dfs(trie[u][0],val         ,dep-1);//先遍历0
    if(trie[u][1]) dfs(trie[u][1],val+(1<<(dep-1)),dep-1);//再遍历1
}

完整代码如下:

#include<cstdio>
#define ll long long
#define N 100000*30+5
using namespace std;
int n,trie[N][2],num[N],tot;
//insert函数，dfs函数已给出
int main(){
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        insert(x);
    }
    dfs(0,0,30);
    return 0;
}

3.算法评价

时间复杂度: O(nlog_2W)

空间复杂度: O(nlog_2W)

其中 W 为值域。

总的来说,01-trie排序常数还是有点大的，也比较费空间，所以并不推荐使用。但是代码量比较小（似乎只有归并码量比它小，但归并不好写），也比较好写。

最后实践比较以下各种排序算法：