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 排序稳定性对比

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中系统实现的快速排序