allbet网址:《算法条记》5. 前缀树、桶排序、排序算法总结

admin/2020-07-17/ 分类:科技/阅读:

目录
  • 1 前缀树结构(trie)、桶排序、排序总结
    • 1.1 前缀树结构
    • 1.2 不基于对照的排序-桶排序
      • 1.2.1 计数排序
      • 1.2.2 基数排序
    • 1.3 排序算法的稳固性
      • 1.3.1 稳固的排序
      • 1.3.2 不稳固的排序
      • 1.3.3 排序稳固性对比
    • 1.4 排序算法总结
    • 1.5 排序常见的坑点
    • 1.6 工程上对排序的改善

1 前缀树结构(trie)、桶排序、排序总结

1.1 前缀树结构

单个字符串中,字符早年到后的加到一颗多叉树上

字符放在路上,节点上有专属的数据项(常见的是pass和end值)

所有样本都这样添加。若是没有路就新建,若是有路就复用

沿途节点的pass值增添1.每个字符串竣事时来到的节点end值增添1

一个字符串数组中,所有字符串的字符数为N,整个数组加入前缀树种的价值是O(N)

功效一:构建好前缀树之后,我们查询某个字符串在不在前缀树中,某字符串在这颗前缀树中泛起了几回都是稀奇利便的。例如找"ab"在前缀树中存在几回,可以先看有无走向a字符的路径(若是没有,直接不存在),再看走向b字符的路径,此时检查该节点的end符号的值,若是为0,则前缀树中不存在"ab"字符串,若是e>0则,e即是几则"ab"在前缀树种泛起了几回

功效二:若是单单是功效一,那么哈希表也可以实现。现查询所有加入到前缀树的字符串,有若干个以"a"字符作为前缀,来到"a"的路径,查看p值巨细,就是以"a"作为前缀的字符串数目

package class05; import java.util.HashMap; public class Code02_TrieTree { public static class Node1 { // pass示意字符从该节点的路径通过 public int pass; // end示意该字符到此节点竣事 public int end; public Node1[] nexts; public Node1() { pass = 0; end = 0; // 每个节点下默认26条路,分别是a~z // 0 a // 1 b // 2 c // .. .. // 25 z // nexts[i] == null i偏向的路不存在 // nexts[i] != null i偏向的路存在 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[] str = word.toCharArray(); // 初始引用指向头节点 Node1 node = root; // 头结点的pass首先 node.pass ; // 路径的下标 int path = 0; for (int i = 0; i < str.length; i ) { // 从左往右遍历字符 // 当前字符减去'a'的ascii码获得需要添加的下个节点下标 path = str[i] - 'a'; // 由字符,对应成走向哪条路 // 当前偏向上没有确立节点,即一开始不存在这条路,新开拓 if (node.nexts[path] == null) { node.nexts[path] = new Node1(); } // 引用指向当前来到的节点 node = node.nexts[path]; // 当前节点的pass node.pass ; } // 当新加的字符串所有字符处置竣事,最后引用指向的当前节点就是该字符串的末端节点,end node.end ; } // 删除该前缀树的某个字符串 public void delete(String word) { // 首先要查一下该字符串是否加入过 if (search(word) != 0) { // 沿途pass-- 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,提前可以得知在本次删除之后,该节点以下的路径不再需要,可以直接删除。 // 那么该节点之下下个偏向的节点引用置为空(JVM垃圾接纳,相当于该节点下的路径被删了) if (--node.nexts[path].pass == 0) { node.nexts[path] = null; return; } node = node.nexts[path]; } // 最后end-- node.end--; } } // 在该前缀树中查找 // 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'; // 寻找该字符串的路径中若是提前找不到path,就是未加入过,0次 if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } // 若是顺遂把word字符串在前缀树中走完路径,那么此时的node对应的end值就是当前word在该前缀树中添加了几回 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'; // 走不到最后,就没有 if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } // 顺遂走到最后,返回的pass就是有若干个字符串以当前pre为前缀的 return node.pass; } } /** * 实现方式二,针对种种字符串,路径不仅仅是a~z对应的26个,用HashMap<Integer, Node2>示意ascii码值对应的node。 **/ public static class Node2 { public int pass; public int end; public HashMap<Integer, Node2> nexts; 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 ; int index = 0; for (int i = 0; i < chs.length; i ) { index = (int) chs[i]; if (!node.nexts.containsKey(index)) { node.nexts.put(index, new Node2()); } node = node.nexts.get(index); node.pass ; } node.end ; } public void delete(String word) { if (search(word) != 0) { char[] chs = word.toCharArray(); Node2 node = root; node.pass--; int index = 0; for (int i = 0; i < chs.length; i ) { index = (int) chs[i]; if (--node.nexts.get(index).pass == 0) { node.nexts.remove(index); return; } node = node.nexts.get(index); } node.end--; } } // word这个单词之前加入过几回 public int search(String word) { if (word == null) { return 0; } char[] chs = word.toCharArray(); Node2 node = root; int index = 0; for (int i = 0; i < chs.length; i ) { index = (int) chs[i]; if (!node.nexts.containsKey(index)) { return 0; } node = node.nexts.get(index); } return node.end; } // 所有加入的字符串中,有几个是以pre这个字符串作为前缀的 public int prefixNumber(String pre) { if (pre == null) { return 0; } char[] chs = pre.toCharArray(); Node2 node = root; int index = 0; for (int i = 0; i < chs.length; i ) { index = (int) chs[i]; if (!node.nexts.containsKey(index)) { return 0; } node = node.nexts.get(index); } return node.pass; } } public static class Right { private HashMap<String, Integer> box; public Right() { box = new HashMap<>(); } public void insert(String word) { if (!box.containsKey(word)) { box.put(word, 1); } else { box.put(word, box.get(word) 1); } } public void delete(String word) { if (box.containsKey(word)) { if (box.get(word) == 1) { box.remove(word); } else { box.put(word, box.get(word) - 1); } } } public int search(String word) { if (!box.containsKey(word)) { return 0; } else { return box.get(word); } } public int prefixNumber(String pre) { int count = 0; for (String cur : box.keySet()) { if (cur.startsWith(pre)) { count = box.get(cur); } } return count; } } // for test public static String generateRandomString(int strLen) { char[] ans = new char[(int) (Math.random() * strLen) 1]; for (int i = 0; i < ans.length; i ) { int value = (int) (Math.random() * 6); ans[i] = (char) (97 value); } return String.valueOf(ans); } // for test public static String[] generateRandomStringArray(int arrLen, int strLen) { String[] ans = new String[(int) (Math.random() * arrLen) 1]; for (int i = 0; i < ans.length; i ) { ans[i] = generateRandomString(strLen); } return ans; } public static void main(String[] args) { int arrLen = 100; int strLen = 20; int testTimes = 100000; for (int i = 0; i < testTimes; i ) { String[] arr = generateRandomStringArray(arrLen, strLen); Trie1 trie1 = new Trie1(); Trie2 trie2 = new Trie2(); Right right = new Right(); for (int j = 0; j < arr.length; j ) { double decide = Math.random(); if (decide < 0.25) { trie1.insert(arr[j]); trie2.insert(arr[j]); right.insert(arr[j]); } else if (decide < 0.5) { trie1.delete(arr[j]); trie2.delete(arr[j]); right.delete(arr[j]); } else if (decide < 0.75) { int ans1 = trie1.search(arr[j]); int ans2 = trie2.search(arr[j]); int ans3 = right.search(arr[j]); if (ans1 != ans2 || ans2 != ans3) { System.out.println("Oops!"); } } else { int ans1 = trie1.prefixNumber(arr[j]); int ans2 = trie2.prefixNumber(arr[j]); int ans3 = right.prefixNumber(arr[j]); if (ans1 != ans2 || ans2 != ans3) { System.out.println("Oops!"); } } } } System.out.println("finish!"); } } 

1.2 不基于对照的排序-桶排序

例如:一个代表员工岁数的数组,排序。数据局限有限,对每个岁数做词频统计。arr[0~200] = 0,M=200

空间换时间

1.2.1 计数排序

桶排序头脑下的排序:计数排序 & 基数排序 1、 桶排序头脑下的排序都是不基于对照的排序 2、 时间庞大度为O(N),二维空间庞大庞大度为O(M) 3、 应用局限有限,需要样本的数据状态知足桶的划分 

瑕玷:与样本数据状态强相关。

1.2.2 基数排序

应用条件:十进制数据,非负

[100,17,29,13,5,27] 举行排序 => 1、找最高位的那个数的长度,这里100的长度为3,其他数前补0,得出 [100,017,029,013,005,027] 2、 准备10个桶,对应的数字0~9号桶,每个桶是一个行列。凭据样本按个位数字对应进桶,相同个位数字进入行列,再从0号桶以此倒出,行列先进先出。个位进桶再依次倒出,得出: [100,013,005,017,027,029] 3、 再把根据个位进桶倒出的样本,再按十位进桶,再按相同规则倒出得: [100,005,013,017,027,029] 4、再把获得的样本按百位进桶,倒出得: [005,013,017,027,029,100] 此时到达有序! 

头脑:先按列位数字排序,列位数字排好序,再用十位数字的顺序去调整,再按百位顺序调整。优先级依次递增,百位优先级最高,百位优先级一样默认根据上一层十位的顺序...

结论:基于对照的排序,时间庞大度的极限就是O(NlogN),而不基于对照的排序,时间庞大度可以到达O(N)。在面试或刷题,估算排序的时间庞大度的时刻,必须用基于对照的排序来估算

/** * 计数排序 **/ package class05; import java.util.Arrays; public class Code03_CountSort { // 计数排序 // only for 0~200 value public static void countSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i ) { max = Math.max(max, arr[i]); } int[] bucket = new int[max 1]; for (int i = 0; i < arr.length; i ) { bucket[arr[i]] ; } int i = 0; for (int j = 0; j < bucket.length; j ) { while (bucket[j]-- > 0) { arr[i ] = j; } } } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize 1) * Math.random())]; for (int i = 0; i < arr.length; i ) { arr[i] = (int) ((maxValue 1) * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i ) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i ) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i ) { System.out.print(arr[i] " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 150; boolean succeed = true; for (int i = 0; i < testTime; i ) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); countSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); countSort(arr); printArray(arr); } } 

下面代码的头脑:

例如原数组[101,003,202,41,302]。获得按个位的词频conut数组为[0,2,2,1,0,0,0,0,0,0]。通过conut词频累加获得conut'为[0,2,4,5,5,5,5,5,5,5],此时conut'的寄义示意个位数字小于即是0的数字有0个,个位数字小于即是1的有两个,个位数字小于即是2的有4个......

获得conut'之后,对原数组[101,003,202,41,302]从右往左遍历。凭据基数排序的头脑,302应该是2号桶最后被倒出的,我们已经知道个位数字小于即是2的有4个,那么302就是4其中的最后一个,放在help数组的3号位置,响应的conut'小于即是2位置的词频减减变为3。同理,41是1号桶的最后一个,个位数字小于即是1的数字有两个,那么41需要放在1号位置,小于即是1位置的词频减减变为1,同理......

实质增添conut和count'结构,制止申请十个行列结构,不想炫技直接申请10个行列结构,按基数排序头脑直接做没问题

实质上,基数排序的时间庞大度是O(Nlog10max(N)),log10N示意十进制的数的位数,然则我们以为基数排序的应用样本局限不大。若是要排随便位数的值,严酷上就是O(Nlog10max(N))

/** * 基数排序 **/ package class05; import java.util.Arrays; public class Code04_RadixSort { // 非负数,十进制,若是负数需要深度改写这个方式 // only for no-negative value public static void radixSort(int[] arr) { if (arr == null || arr.length < 2) { return; } radixSort(arr, 0, arr.length - 1, maxbits(arr)); } // 盘算数组样本中最大值的位数 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 ; max /= 10; } return res; } // arr[l..r]排序 , digit:最大值的位数 // l..r [3, 56, 17, 100] 3 public static void radixSort(int[] arr, int L, int R, int digit) { // 由于十进制的数,我们依10位基底 final int radix = 10; int i = 0, j = 0; // 有若干个数准备若干个辅助空间 int[] help = new int[R - L 1]; for (int 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的话 d是1示意个位 取出j=3 // 209 1 9 j = getDigit(arr[i], d); count[j] ; } // conut往conut'的转化 for (i = 1; i < radix; i ) { count[i] = count[i] count[i - 1]; } // i从最后位置往前看 for (i = R; i >= L; i--) { j = getDigit(arr[i], d); help[count[j] - 1] = arr[i]; // 词频-- count[j]--; } // 处置完个位十位...之后都要往原数组copy for (i = L, j = 0; i <= R; i , j ) { arr[i] = help[j]; } } } public static int getDigit(int x, int d) { return ((x / ((int) Math.pow(10, d - 1))) % 10); } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize 1) * Math.random())]; for (int i = 0; i < arr.length; i ) { arr[i] = (int) ((maxValue 1) * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i ) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i ) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i ) { System.out.print(arr[i] " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100000; boolean succeed = true; for (int i = 0; i < testTime; i ) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); radixSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); radixSort(arr); printArray(arr); } } 

1.3 排序算法的稳固性

稳固性是指同样巨细的样本在排序之后不会改变相对顺序。基础类型稳固性没意义,用处是按引用通报后是否稳固。好比学生有班级和岁数两个属性,先按班级排序,再按岁数排序,那么若是是稳固性的排序,不会损坏之前已经按班级拍好的顺序

稳固性排序的应用场景:购物时刻,先按价钱排序商品,再按好评度排序,那么好评度着实价钱排好序的基础上。反之不稳固排序会损坏一开始根据价钱排好的顺序

1.3.1 稳固的排序

1、 冒泡排序(处置相等时不交流)

2、 插入排序(相等不交流)

3、 合并排序(merge时刻,相等先copy左边的)

1.3.2 不稳固的排序

1、 选择排序

2、 快速排序 (partion历程无法保证稳固)

3、 堆排序 (维持堆结构)

1.3.3 排序稳固性对比

排序 时间庞大度 空间庞大度 稳固性
选择排序 O(N^2) O(1)
冒泡排序 O(N^2) O(1)
插入排序 O(N^2) O(1)
合并排序 O(NlogN) O(N)
随机快拍 O(NlogN) O(logN)
堆排序 O(NlogN) O(1)
计数排序 O(N) O(M)
堆排序 O(N) O(N)

1.4 排序算法总结

  1. 不基于对照的排序,对样本数据有严酷要求,不易改写
  2. 基于对照的排序,只要规定好两个样本怎么对照巨细就可以直接复用
  3. 基于对照的排序,时间庞大度的极限是O(NlogN)
  4. 时间庞大度O(NlogN)、分外空间庞大度低于O(N),且稳固的基于对照的排序是不存在的
  5. 为了绝对的速率选择快排(快排的常数时间低),为了节约空间选择堆排序,为了稳固性选合并

1.5 排序常见的坑点

合并排序的额为空间庞大度可以变为O(1)。“合并排序内部缓存法”,然则将会变的不稳固。不思量稳固不如直接选择堆排序

“原地合并排序”是垃圾帖子,会让时间庞大度酿成O(N ^2)。时间庞大度退到O(N ^2)不如直接选择插入排序

快速排序稳固性改善,“01 stable sort”,然则会对样本数据要求更多。对数据举行限制,不如选择桶排序

在整形数组中,请把奇数放在数组左边,偶数放在数组右边,要求所有奇数之间原始顺序稳定,所有偶数之间原始顺序稳定。要求时间庞大度O(N),额为空间庞大度O(1)。这是个01尺度的partion,奇偶规则,然则快速排序的partion历程做不到稳固性。以是正常实现不了,学术论文(01 stable sort,不建议碰,对照难)中需要把数据阉割限制之后才气做到

1.6 工程上对排序的改善

稳固性思量:值通报,直接快排,引用通报,合并排序

充分利用O(NlogN)和O(N^2)排序各自的优势:凭据样本量底层基于多种排序实现,好比样本量对照小直接选择插入排序。

好比Java中系统实现的快速排序

,

平心在线官网

欢迎进入平心在线官网(原诚信在线、阳光在线)。平心在线官网www.px111.net开放平心在线会员登录网址、平心在线代理后台网址、平心在线APP下载、平心在线电脑客户端下载、平心在线企业邮局等业务。

TAG:
阅读:
广告 330*360
广告 330*360

热门文章

HOT NEWS
  • 周榜
  • 月榜
Sunbet_进入申博sunbet官网
微信二维码扫一扫
关注微信公众号
新闻自媒体 Copyright © 2002-2019 Sunbet 版权所有
二维码
意见反馈 二维码