• 前缀树及计数排序、基数排序、排序算法拓展【十大经典排序】

    前缀树及计数排序、基数排序【十大经典排序】

    1 前缀树（prefix tree/trie）

    1. 单个字符串中，字符从前到后的加到一棵多叉树上
    2. 字符放在路上，节点上有专属的数据项（常见的就是pass和end值）
    3. 所有样本都这样添加，如果没有路就新建，如果有路就复用
    4. 沿途节点的pass值增加1，每个字符串结束时来到的节点end值增加1

    1.1 前缀树设计思路

    例子
    设计一种结构，用户可以：

    • void insert(String str) 添加某个字符串，可以重复添加，每次算1个
    • int search(String str) 查询某个字符串在结构中还有几个
    • void delete(String str) 删除某个字符串，可以重复删除，每次算1个
    • int prefixNumber(String str) 查询有多少个字符串，是以str作前缀的

    前缀树的实现方式：

    1）固定数组实现
    2）哈希表实现

    1.2 代码实现

    1.2.1 前缀树节点Node（组成元素）

    //前缀树节点
public static class Node1{
    //经过次数
    private int pass;
    //结尾次数
    private int end;
    //横向数组【路径选择】
    private Node1[] nexts;

    public Node1(){
        this.pass = 0;
        this.end = 0;
        //字符串，一共26种字母组成【26种路径】
        nexts = new Node1[26];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    1.2.2 添加元素insert(String word)

    //添加字符串
public void insert(String word){
    if(word == null){
        return;
    }
    char[] chs = word.toCharArray();
    Node1 node = root;
    //添加元素，经过root的pass++
    node.pass++;
    int path = 0;
    for(int i = 0; i < chs.length; i++){
        //找到是哪条路径
        path = chs[i] - 'a';
        //该路径上没有字母，新建【有：pass++】
        if(node.nexts[path] == null){
            node.nexts[path] = new Node1();
        }
        //继续向下走
        node = node.nexts[path];
        node.pass++;
    }
    node.end++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    1.2.3 删除单词/路径 delete(String word)

    //删除前缀树的单词【删除一条路径】
public void delete(String word){
    //先判断该单词是否存在于树中
    if(search(word) != 0){
        char[] chs = word.toCharArray();
        Node1 node = root;
        //路径从根开始
        node.pass--;
        int path = 0;
        for(int i = 0; i < chs.length; i++){
            path = chs[i] - 'a';
            //先--，如果pass为0，就将其设为null
            if(--node.nexts[path].pass == 0){
                node.nexts[path] = null;
                return;
            }
            node = node.nexts[path];
        }
        node.end--;
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    1.2.4 搜寻某个字符串出现次数/几条路径 search(String word)

    //搜寻某个单词在树中出现了几次
public int search(String word){
    if(word == null){
        return 0;
    }
    char[] chs = word.toCharArray();
    //从根节点开始向下找
    Node1 node = root;
    int index = 0;
    for(int i = 0; i < chs.length; i++){
        //走哪条路径
        index = chs[i] - 'a';
        if(node.nexts[index] == null){
            return 0;
        }
        node = node.nexts[index];
    }
    return node.end;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    1.2.5 以pre为前缀的单词个数prefixNumber(String pre)

    //所有加入的字符串中，有多少以pre作为前缀
public int prefixNumber(String pre){
    if(pre == null){
        return 0;
    }
    char[] chs = pre.toCharArray();
    Node1 node = root;
    int index = 0;
    for(int i = 0; i < chs.length; i++){
        index = chs[i] - 'a';
        //该路径下面为null，直接返回0
        if(node.nexts[index] == null){
            return 0;
        }
        node = node.nexts[index];
    }
    return node.pass;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    1.2.6 全部代码

    //前缀树节点
public static class Node1{
    //经过次数
    private int pass;
    //结尾次数
    private int end;
    //横向数组【路径选择】
    private Node1[] nexts;

    public Node1(){
        this.pass = 0;
        this.end = 0;
        //字符串，一共26种字母组成【26种路径】
        nexts = new Node1[26];
    }
}

public static class Trie1{
    //根节点
    private Node1 root;

    public Trie1(){
        root = new Node1();
    }

    //添加字符串
    public void insert(String word){
        if(word == null){
            return;
        }
        char[] chs = word.toCharArray();
        Node1 node = root;
        //添加元素，经过root的pass++
        node.pass++;
        int path = 0;
        for(int i = 0; i < chs.length; i++){
            //找到是哪条路径
            path = chs[i] - 'a';
            //该路径上没有字母，新建【有：pass++】
            if(node.nexts[path] == null){
                node.nexts[path] = new Node1();
            }
            //继续向下走
            node = node.nexts[path];
            node.pass++;
        }
        node.end++;
    }

    //删除前缀树的单词【删除一条路径】
    public void delete(String word){
        //先判断该单词是否存在于树中
        if(search(word) != 0){
            char[] chs = word.toCharArray();
            Node1 node = root;
            //路径从根开始
            node.pass--;
            int path = 0;
            for(int i = 0; i < chs.length; i++){
                path = chs[i] - 'a';
                //先--，如果pass为0，就将其设为null
                if(--node.nexts[path].pass == 0){
                    node.nexts[path] = null;
                    return;
                }
                node = node.nexts[path];
            }
            node.end--;
        }

    }


    //搜寻某个单词在树中出现了几次
    public int search(String word){
        if(word == null){
            return 0;
        }
        char[] chs = word.toCharArray();
        //从根节点开始向下找
        Node1 node = root;
        int index = 0;
        for(int i = 0; i < chs.length; i++){
            //走哪条路径
            index = chs[i] - 'a';
            if(node.nexts[index] == null){
                return 0;
            }
            node = node.nexts[index];
        }
        return node.end;
    }

    //所有加入的字符串中，有多少以pre作为前缀
    public int prefixNumber(String pre){
        if(pre == null){
            return 0;
        }
        char[] chs = pre.toCharArray();
        Node1 node = root;
        int index = 0;
        for(int i = 0; i < chs.length; i++){
            index = chs[i] - 'a';
            //该路径下面为null，直接返回0
            if(node.nexts[index] == null){
                return 0;
            }
            node = node.nexts[index];
        }
        return node.pass;
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113

    2 不基于比较的排序【桶排序】

    桶排序思想下的排序：计数排序 & 基数排序
    1)桶排序思想下的排序都是不基于比较的排序
    2)时间复杂度O（N），空间复杂度O（M）
    3)应用范围有限，需要样本的数据状况来满足桶的划分

    计数排序和基数排序

    • 一般来讲，计数排序，要求样本是整数，且范围窄小【每一个都列出来】
    • 一般来讲，基数排序，要求样本是10进制的正整数（可以为负，需要改写，同时加上负数的绝对值【越界问题】）

    2.1 计数排序

    //计数排序
public static void countSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    int max = Integer.MIN_VALUE;
    for(int i : arr){
        max = Math.max(i, max);
    }
    //创建桶【假设最大值是14】
    // 【0 1 2 3 4 .....13 14】
    int[] buckets = new int[max+1];
    //入桶
    for(int i = 0; i < arr.length; i++){
        buckets[arr[i]]++;
    }
    //出桶【从小的出】
    int index = 0;
    for(int j = 0; j < buckets.length; j++){
        while(buckets[j]-- > 0){
            arr[index++] = j;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    2.2 基数排序

    进阶写法：不用创建多个桶，直接在help数组上修改

    //基数排序：arr中只能为正值【如果有负值，需要做特殊处理】
public static void radixSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    radixSort(arr, 0, arr.length - 1, maxbits(arr));
}

//获取arr中的最大位数【循环几次】
public static int maxbits(int[] arr){
    int max = Integer.MIN_VALUE;
    for(int i : arr){
        max = Math.max(max, i);
    }
    int res = 0;
    while (max != 0){
        max /= 10;
        res++;
    }
    return res;
}

//arr[L, R]排序       digit：最大的十进制位数
public static void radixSort(int[] arr, int L, int R, int digit){
    final int radix = 10;
    int i = 0, j = 0;
    //有多少个数，准备多少个辅助空间
    int[] help = new int[R - L + 1];
    //有多少位，就进出多少次
    for(int d = 1; d <= digit; d++){
        //count -> count' [前缀和]
        //10个空间
        //count[0] 当前位【d位】是0的的数字有多少个【个、十、百、...】
        //count[1] 当前位【d位】是0和1的数字有多少个
        //count[2] 当前位【d位】是0、1、2的数字有多少个(<=2)
        //count[i] 当前位【d位】是0~i的数字有多少个
        int[] count = new int[radix]; //count[0...9]
        for(i = L; i <= R; i++){
            j = getDigit(arr[i], d);
            count[j]++;
        }
        for(i = 1; i < radix; i++){
            //变为前缀和count[1]表明<=1的数有几个
            count[i] = count[i] + count[i-1];
        }
        for(i = R; i >= L; i--){
            j = getDigit(arr[i], d);
            help[count[j] - 1] = arr[i];
            count[j]--;
        }
        for(i = L, j = 0; i <= R; i++, j++){
            arr[i] = help[j];
        }
    }
}

//获取x每一位的数值
public static int getDigit(int x, int d){
    return ((x / (int) Math.pow(10, d - 1)) % 10);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    3 排序算法拓展

    3.1 排序算法的稳定性

    • 稳定性是指同样大小得样本再次排序之后不会改变相对次序
      比如：2 1 3 1 5
      排序完成之后 1 1 2 3 5，第一个1还是在第二个1后面，那么该排序算法就是稳定的，反之不稳定
    • 对基础类型来说，稳定性毫无意义【因为没有实际应用场景】
    • 对非基础类型来说，稳定性有意义
      比如：一个Student数组，原本按照年龄age顺序排列好了，现在要求按照排序排序
      那么，具有稳定性的排序算法排序完成之后，该数组中便是Student按照班级排序，且内部按照年龄排序
    • 有些排序算法可以实现成稳定的，而有些排序算法无论如何都实现不成稳定的

    3.2 排序算法比较

    在这里插入图片描述
    注：希尔排序也是不稳定的，时间复杂度O（N*logN）

    1. 基于比较类的排序，时间复杂度极限：O（N*logN）
    2. 时间复杂度O（N*logN）、额外空间复杂度低于O（N）且稳定的基于比较的排序是不存在的
    3. 为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并

    工程上对于排序的改进：
    1）稳定性考虑

    Java内部的Arrays.sort()内部是改良后的快排，会根据传入的参数是否是基础类型，如果是基础类型，对稳定性无要求，直接快排，如果非基础类型，有稳定性要求，走归并

    2）充分利用O（N*logN）和O(N^2)排序各自的优势

    快排如果L + 60 > R 内部直接走插入（常数项小）

  • 相关阅读:
    民办二本计算机毕业以后
    媒体行业的3D建模：在影视中创造特效纹理
    Linux 下的截屏并编辑的工具-flamshot安装及使用
    Android 12.0系统申请动态权限之高德定位
    一：图形的位置和尺寸测量
    Docker安装与应用全套讲解
    【SpringBoot】71、SpringBoot中集成多数据源+动态数据源
    S2B2C供应链系统将引领商业模式！S2B2C供应链电商系统实现订单管理数智化
    完全卸载清理干净xcode
    Vulnhub: Masashi: 1靶机
  • 原文地址：https://blog.csdn.net/weixin_45565886/article/details/126297113