前缀树
- 单个字符串中,字符从前到后的加到一颗多叉树上
- 字符放在路上,节点上有专属的数据项(常见的是pass和end值)
- 所有样本都这样添加,如果没有路就新建,如有路就复用
- 沿途节点的pass值增加1,每个字符串结束时来到的节点end值增加1
可以完成前缀相关的查询
package com.harrison.five; import java.util.HashMap; public class Code02_TrieTree { // 字符串是所有的小写字母 public static class Node1 { public int pass; public int end; public Node1[] nexts; // 0 a // 1 b // ... // 25 z public Node1() { pass = 0; end = 0; nexts = new Node1[26]; } } public static class Trie1 { public 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++; int path = 0; for (int i = 0; i < str.length; i++) {// 从左往右遍历字符 path = str[i] - 'a';// 由字符,对应成走向哪条路 if (node.nexts[path] == null) {// 无节点新建,有节点复用 node.nexts[path] = new Node1(); } node = node.nexts[path]; node.pass++; } node.end++; } // word这个单词之前加入过几次 public int search(String word) { if (word == null) { return 0; } char[] str = word.toCharArray(); Node1 node = root; int path = 0; for (int i = 0; i < str.length; i++) { path = str[i] - 'a'; if (node.nexts[path] == null) { return 0; } node = node.nexts[path]; } return node.end; } public void delete(String word) { if (search(word) != 0) { char[] str = word.toCharArray(); Node1 node = root; int path = 0; for (int i = 0; i < str.length; i++) { path = str[i] - 'a'; if (--node.nexts[path].pass == 0) { node.nexts[path] = null; return; } node = node.nexts[path]; } node.end--; } } // 所有加入的字符串中,有几个是以pre这个字符串作为前缀的 public int prefixNumber(String word) { if (word == null) { return 0; } char[] str = word.toCharArray(); Node1 node = root; int path = 0; for (int i = 0; i < str.length; i++) { path = str[i] - 'a'; if (node.nexts[path] == null) { return 0; } node = node.nexts[path]; } return node.pass; } } 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 { public Node2 root; public Trie2() { root = new Node2(); } public void insert(String word) { if (word == null) { return; } char[] str = word.toCharArray(); Node2 node = root; node.pass++; int path = 0; for (int i = 0; i < str.length; i++) {// 从左往右遍历字符 path = (int) str[i]; if (!node.nexts.containsKey(path)) {// 无节点新建 node.nexts.put(path, new Node2()); } // 有节点复用 node = node.nexts.get(path); node.pass++; } node.end++; } // word这个单词之前加入过几次 public int search(String word) { if (word == null) { return 0; } char[] str = word.toCharArray(); Node2 node = root; int path = 0; for (int i = 0; i < str.length; i++) { path = (int) str[i]; if (!node.nexts.containsKey(path)) { return 0; } node = node.nexts.get(path); } return node.end; } public void delete(String word) { if (search(word) != 0) { char[] str = word.toCharArray(); Node2 node = root; int path = 0; for (int i = 0; i < str.length; i++) { path = (int) str[i]; if (--node.nexts.get(path).pass == 0) { node.nexts.remove(path); return; } node = node.nexts.get(path); } node.end--; } } // 所有加入的字符串中,有几个是以pre这个字符串作为前缀的 public int prefixNumber(String word) { if (word == null) { return 0; } char[] str = word.toCharArray(); Node2 node = root; int path = 0; for (int i = 0; i < str.length; i++) { path = (int) str[i]; if (!node.nexts.containsKey(path)) { return 0; } node = node.nexts.get(path); } 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; } } 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); } 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)时间复杂度为O(N),额外空间复杂度为O(M)
3)应用范围有限,需要样本的数据状况满足桶的划分
弱点(极大):必须和样本的数据状况强相关,所以桶排序下的排序都对数据状况有要求
- 一般来讲,计数排序要求,样本是整数,且范围比较窄
- 一般来讲,基数排序要求,样本是10进制的正整数
- 一旦要求稍有升级,改写代价增加是显而易见的
计数排序
package com.harrison.five; import java.util.Arrays; public class Code03_CountSort { 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; } } } 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); } }
基数排序
package com.harrison.five; 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 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++) {// 有多少位就进出多少次 // 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 1 9 j = getDigit(arr[i], d); count[j]++; } for (i = 1; i < radix; i++) { 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[i]; } } } public static int getDigit(int x, int d) { return ((x / ((int) Math.pow(10, d - 1))) % 10); } 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); } }
排序总结
时间复杂度 | 额外空间复杂度 | 稳定性 | |
选择排序 | O(N^2) | O(1) | 无 |
冒泡排序 | O(N^2) | O(1) | 有 |
插入排序 | O(N^2) | O(1) | 有 |
归并排序 | O(N*logN) | O(N) | 有 |
随机快排 | O(N*logN) | O(logN) | 无 |
堆排序 | O(N*logN) | O(1) | 无 |
计数排序 | O(N) | O(M) | 有 |
基数排序 | O(N) | O(N) | 有 |
- 不基于比较的排序,对样本数据有严格要求,不易改写
- 基于比较的排序,只要规定好两个样本怎么比大小就可以直接复用
- 基于比较的排序,时间复杂度的极限是O(N*logN)
- 时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的
- 为了绝对的速度选快排,为了节省空间选堆排,为了稳定性选归并
常见的坑
- 归并排序的额外空间复杂度可以变成O(1),“归并排序 内部缓存法”,但是将变得不在稳定——直接用堆
- “原地归并排序”是垃圾贴,会让时间复杂度变成O(N^2)——插排
- 快速排序稳定性改进,“01 stable sort”,但是会对样本数据要求更多——桶排
- 在整型数组中,请把奇数放在数组左边,偶数放在数组右边,要求所有奇数之间原始的相对次序不变,所有偶数之间的相对次序不变。时间复杂度做到O(N),额外空间复杂度做到O(1)——快排不稳定