Trie前缀树、桶排序、排序总结
Trie前缀树、桶排序、排序总结
前缀树
单个字符串中，字符从前到后的加到一颗多叉树上
字符放在路上，节点上有专属的数据项
所有样本都这样添加，如果没有路就新建，如果有路就复用，
沿途节点的pass值增加1，每个字符串结束时来到的结点end值增加1
可以完成前缀相关的查询
前缀树的建立过程：
有一个pass值代表经过此结点的路径的数量
有一个end值代表以此结点为结尾的字符串数量
如何查询一个字符串在前缀树中加入了多少次？
先沿着所给字符串把前缀树走一遍，如果可以走到end结点，直接查询此结点的的end值即为此字符串加入的次数
如何查询一字符被当作了多少次前缀？
直接查看这个字符的p值即可
下面来看一下前缀树的代码：(第一种实现方式)
public static class Node1 {
public int pass;
public int end;
public Node1[] next;
public Node1() {
pass = 0;
end = 0;
nexts = new Node1[26];
//最多只有26个字母，26条路
//数组中0下标对应的是到a的路，1下标对应的是到b的路，2下标对应的是到c的路...25下标对应的是到z的路
//if(next[i] == null) i方向上的路不存在，否则存在
}
public class Trie1 {
private Node1 root;
public Trie1() {
root = new Node1();
}
public void insert(String word) {
if(word == null) {
return;
}
char[] str = word.toCharArray(); //第一步：先把它转换成一个字符类型的数组
//然后，你只要添加一个字符串都是从头结点开始添加的
//所以我准备一个引用，这个引用是从头结点开始的
Node1 node = root;
node.pass++; //头结点下面准备加入字符串，所以头结点的pass值可以先++
int path = 0;
//下面这个for循环可厉害了
for(int i = 0; i < str.length; i++) {
path = str[i] - 'a'; //用对应加入的字符的ASCII码减去a的ASCII码，这样a的path就是0，b的 path是1，c的path是2...以此类推，对应成走哪条路
if(node.nexts[path] == null) {
node.nexts[path] = new Node1(); //在这个方向上建出一个新结点来
//nexts数组中的数据类型是Node1结点型的(有点像链表)
}
node = node.nexts[path];
node.pass++;
//建完这个结点之后，node跳到这个结点上来，并且来到它之后把它的path值++
}
node.end++;
}
}
//查询一个字符串之前加入了多少次
public int search(String word) {
if(word == null) {
return 0;
}
char[] chs = word.toCharArray(); //直接把字符串转换成字符类型的数组
Node1 node = root;
int index = 0; //这几步和创建数组的时候都一样，区别就是在查找的时候不要让它的p值和e值++
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 < cha.length; i++) {
index = chs[i] - 'a';
if(node.next[index] == null) {
return 0;
}
node = node.next[index];
}
return node.pass;
}
//删除字符串操作(整体思路：删除的时候，沿途p--，到最后一个字符的时候e--)
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';
if(--node.next[path].pass == 0) {
node.next[path] == null;
return;
}
node = node.nexts[path];
}
node.end--;
}
}
第一种实现方式只有字符串是26个字母小写才行，如果字符种类变得特别多呢？
前缀树第二种实现方式：
//当你的字符种类很多的时候，用哈希表的形式来表示
public static class Node2 {
public int pass;
public int end;
public HashMap<Integer, Node2> nexts;
//第一个Integer值代表此结点的对应的path值(a=0,b=1...z=25)
public Node2() {
pass = 0;
end = 0;
nexts = new HashMap<>();
}
public static class Trie2 {
private Node2 root;
public Trie2() {
root = new Node2();
}
public void insert(String word) {
if(word == null) {
return;
}
char[] chs = word.toCharArray();
Node2 node = root;
node.pass++; //剩下的和上面的一模一样
}
}
}
//本结的代码中有code1和code2，其中code1有一点问题。下来自己用对数器跑一下看一下code1哪里出了问题。是一个非常好的可以练习使用对数器的例子(对数器自己写)
不基于比较的排序
桶排序
题目1：一个数组中存放着员工的年龄，员工的年龄在0-200之间不等，请设计一个排序将数组排序
如何将排序快一点做完？——对每一个年龄做词频统计。整体思路是这样，建立一个help数组，里面存放201个数，下标分别对应0-200。每个下标位置代表员工的年龄，下标中存储的数代表员工年龄的词频数。
这是一个时间复杂度为O(N)的排序，叫做计数排序（从数组下标0开始往后遍历一遍）。这种排序与我们之前讲过的排序有区别，它是完全不基于比较的，这种不基于比较的排序就叫做桶排序。记数排序就是桶排序的一种体现。这题相当于你建了两百个桶，桶就是容器的意思，可以是一个队列、一个栈...这里的桶就是我们的词频。但是这个排序是有极大的弱点的，它必须和它的数据的状况强相关，比如这题范围是0-200，那就有201个桶。范围小的时候计数排序才有用。所有桶排序思想下的排序都对数据状况本身有要求。
桶排序的第二种具体实现：基数排序
通常来讲经典的基数排序中的数都是非负的十进制数。
数组中有多少个数就建立多少个桶，桶的形式是队列。先把各个数的个位入队，然后从0队依次出队，一直到9队出完。然后十位数字入队，从0到9依次出队，最后百位数入队，从0到9依次出队。
注意：你在刷题或面试的过程中，除非特殊声明，否则使用的排序都必须是基于比较的排序
计数排序的代码（上图），太简单了，懒得敲。
基数排序代码：
public static void radixSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1; maxbits(arr)); //这是一个另一个方法，重载方法
}
//maxbits是用来算digit的，最大的数有多少位。先把最大数找到，每一次除以10，然后位数++
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for(int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int res = 0;
while(max != 0) {
res++,
}
}
//arr[L...R]排序，digit
//digit代表的数是数组中最大的数有多少位
public static void radixSort(int[] arr, int L, int R, int digit) {
final int radix = 10; //以10为基底
int i = 0, j = 0;
int[] help = new int[R - L + 1];
for(d = 1; d <=digit; d++) { //有多少位就进出多少次
//10个空间
//count[0]当前位(d位)是0的数字有多少个
//count[1]当前位(d位)是0和1的数字有多少个
//count[2]当前位(d位)是0、1和2的数字有多少个
//count[i]当前位(d位)是0-i的数字有多少个
int count = new int[radix]; //count[0..9]
for(i = L; i <= R; i++) {
//103 1 3
//209 2 0
j = getDigit(arr[i], d); //获得arr[i]中的第d位数
count[j]++;
}
for(i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1]; //然后count在自己上面做累加和，然后count变成count'
}
for(i = R; i >= L; i--) {
j = getDigit(arr[i], d); //找到当前数组中数字的第i位数是多少，赋给j
help[count[j] - 1] = arr[i]; //找到了那个数的某一位之后在count中取出来，对应地找到原来的整数， 并放入help中（count中下标是i，放入help数组中下标就是i-1）
count[j]--; //不要忘了词频减减
//这个循环结束时候help里面装的就是我们从桶中倒出来的东西
}
for(i = L; j = 0; i <= R; i++; j++) {
arr[i] = help[j]; //然后把help里面的东西拷贝回arr里面
}
//然后最上面d++，d=2继续，d=3继续...一直到最大位digit
}
}
//这个实现可以说是非常6了，如果你实在懒得想，搞十个队列来写也不是不可以，但越简单越好
help数组的代码实现，下面是一个图解：(for循环中的内容)
桶排序思想下的排序：计数排序&基数排序
时间复杂度为O(N)，额外空间负载度O(M)
应用范围有限，需要样本的数据状况满足桶的划分
计数排序和基数排序
一般来讲，计数排序要求，样本是整数，且范围比较窄
一般来讲，基数排序要求，样本是10进制的整数
一旦要求稍有升级，改写代价增加是显而易见的
排序算法的稳定性
稳定性是指同样大小的样本再排序之后不会改变相对次序
对基础类型来讲说，稳定性毫无意义
对非基础类型来说，稳定性有重要意义
有些排序算法可以实现为稳定的，而有些排序算法无论如何都实现不成稳定的
因为基础类型按值传递，所以稳定性没啥用，它的用处是按引用传递的那些内容
比如现在你要对学生这个类型进行排序，先按照班级进行排序，班级排序完了之后按照年龄进行排序。如果你的排序是稳定型排序，那么你的年龄排序结构排序完的结果将会是一班年龄从小到大，二班年龄从小到大...这个是可以用比较器来写主条件和次条件，但如果有7个属性，每个属性都要保证稳定，你怎么写？
下面我们来分析一下之前学过的排序哪些是稳定的。分析稳定性一定是建立在你对流程巨熟悉的基础上。如果你觉得你有一点点困惑，一定要看一下前几个排序（八大排序目前所有文章加起来刚好写完）。
选择排序有没有稳定性？没有。
0~n-1之间要把最小的数放到0位置去，第一个5跑到1那个位置去了，相对位置变化，不稳定
冒泡排序有没有稳定性？有。你处理相等元素时的态度，就决定了排序的稳定性能不能实现。冒泡排序相等的时候元素不交换，保留了其稳定性
冒泡排序：从第一个元素开始和后面的元素进行比较，谁大谁往后走，相等时不交换。这个特性决定了冒泡排序是稳定的排序
插入排序是否稳定？稳定。元素相等时不交换
三个经典的n^2排序我们就处理完了，接下来我们看归并排序。
归并排序处理相等元素时的态度，如果元素相等时先拷贝左组元素，则稳定。但如果你要具体修改merge中的功能，先拷贝右边的，排序的功能不会被破坏，但是稳定性会受到破坏。总而言之就是相等时先拷贝右边的，稳定性就会被破坏
快速排序。稳定不了。三个版本都稳定不了，因为partition过程就是做不了稳定的
上图中画圈的6原来是在3的位置，3和6交换后小于等于区域++，做不到稳定。
堆排序。不稳定。因为人家根本不管你稳定不稳定，它只管自己的堆结构有没有调好。
上图中4本来是在数组最后，往上看和它的父结点3交换了（将此数组变成一个大根堆的过程）
选择排序最差，时间复杂度都O(N^2)了还做不到稳定，太拉给了。
归并要准备额外空间做merge。
下面，私货，常见的坑。你们学习的时候如果遇到下面的坑，至少每一个都坑你一个星期
归并排序搞成O(1)，舍弃稳定性，直接用堆排啊大哥，有必要搞这么复杂吗？你要真的去了解归并排序内部缓存法，至少一个星期
原地归并排序让空间复杂度变成O(1)，时间复杂度变成O(N^2)，求你去写插排，插排常数项又低，时间复杂度也是O (N^2)
快速排序更改稳定性，但是它要求你对数据范围做限制...你tm在逗我吧？快排就是基于比较的排序，如果你要求我对数据状况做出限制，我为什么不用桶排序呢？
它是一个01标准的partition，不是小于就是大于。奇偶也是01标准，那我们快排经典的partition过程是做不到稳定性的，如果你这个能做到稳定，那为什么快排不改成稳定的呢？如果你对面试官问这个问题，面试官马上疯给你看。因为他就是在故意难为你，他根本就不会。这种题就是故意出来给你压价压薪水的，这种见一次怼一次，有机会的话，干他。
根据需求选择不同的排序
快排和堆排是调度优秀，但是常数时间不够好，但插入排序常数时间很优秀。于是，小样本量时，快排直接终止调度，对剩下那一小部分进行插入排序后直接返回。
这些都是经常遇到的优化。