本文共 27937 字，大约阅读时间需要 93 分钟。
归并排序的实质就是先将节点全部分离，然后亮亮合并，合并过程中用到了一个辅助数组，所以时间复杂度为O(nlogn),空间复杂度为O(N)。可以解决的问题通常跟一个数组中两个数的位置移动有关系，比如比当前数大的个数和之类的问题。
package niuke.zuoshen;/** * 归并排序算法 + 随机数组产生器 * @author tangyuan * * 2019年7月7日 *CopyRight:Copyright(c)2019
*/public class MergeSort { public static void mergeSort(int[] arr){ if(arr == null || arr.length < 2) return; mergeSort(arr, 0, arr.length - 1); } private static void mergeSort(int[] arr, int l, int r) { //终止条件 if(l == r) return; int mid = l + (r - l) / 2; mergeSort(arr, l, mid);//拆分左半部分 mergeSort(arr, mid + 1, r);//拆分右半部分 merge(arr, l, mid, r);//每次拆分完之后就合并，合并的都是有序的数组，所以比较块 } //合并的方法有点类似于连个有序链表的合并过程 private static void merge(int[] arr, int l, int mid, int r) { int[] help = new int[r - l + 1];//创建一个辅助数组 int i = 0; int p1 = l;//做部分指针 int p2 = mid +1;//右部分指针 while(p1 <=mid && p2 <= r) { help[i++] = arr[p1] < arr[p2]? arr[p1++] : arr[p2++]; } //两个while循环用来处理剩余部分，必定只执行一个 while(p1 <= mid) help[i++] = arr[p1++]; while(p2 <= r) help[i++] = arr[p2++]; for(int j = 0; j < help.length; j++)//合并成功的部分整理到原数组 arr[l + j] = help[j]; } public static int[] generateRandomArray(int maxSize, int maxValue){ int[] arr = new int[(int)((maxSize + 1) * Math.random())];//Math.random()产生的是一个[0,1)随机数 for(int i = 0; i < arr.length; i++) arr[i] = (int)(((maxValue + 1) * Math.random()) - ((maxValue + 1) * Math.random())); return arr; } public static void main(String[] args) { /* int[] arr = {1,6,3,2,8,0,9}; mergeSort(arr); for(int i = 0; i < arr.length; i++) System.out.println(arr[i]);*/ int[] arr = generateRandomArray(20, 16); mergeSort(arr); for(int i = 0; i < arr.length; i++) System.out.println(arr[i]); }}
堆排序中的堆结构应用广泛，在Java中就是优先队列。可以解决的问题例如TOP（N）的问题，也可以用大小堆解决中位数的问题。
堆排序主要分为两部分，一部分是建堆，然后是排序，每次弹出堆顶元素然后进行调整的过程package niuke.zuoshen;/** * 堆排序 * @author tangyuan * * 2019年7月8日 *CopyRight:Copyright(c)2019
*/public class HeapSort { public static void heapSort(int[] arr){ if(arr == null || arr.length < 1) return; //step1:构建一个大堆顶 for(int i = 0; i < arr.length; i++) heapInsert(arr, i); //step2:根据大堆顶生成有序的数组 int size = arr.length; //step2.1:将堆顶元素与最后元素交换 swap(arr, 0, --size); while(size > 0) { heapify(arr, 0, size); swap(arr, 0, --size); } } /** * 从顶点开始调整，调整的路径长度为log(n) * @param arr * @param index * @param size */ private static void heapify(int[] arr, int index, int size) { int left = index * 2 + 1; int temp = arr[index]; while(left < size) { if(left + 1 < size) { if(arr[left] < arr[left + 1]) left = left + 1; } if(temp < arr[left]) { arr[index] = arr[left]; index = left; left = left * 2 + 1; }else break; } arr[index] = temp; } //构建一个大根堆的时间复杂度为O(N) private static void heapInsert(int[] arr, int i) { while(arr[i] > arr[(i - 1)/2]) { swap(arr, i, (i - 1)/2); i = (i - 1) / 2; } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = { 1,7,6,3,2,0,9,11,23}; heapSort(arr); for(int i = 0; i < arr.length; i++) System.out.println(arr[i]); }}
首先要注意一点就是传统的快速排序有一个很严重的确定，因为每次都是选尾数，所以当数组有序的时候，会退化为O（N^2）的时间复杂度，所以采用随机生成切分数。此外传统的快速排序还有一个缺点就是当数组中存在相同元素的时候，快速排序还是要对每一个相同的元素进行一次快速排序，效率比较低，可以采用荷兰国旗来解决。就是每次不是确定一个数的位置，而是确定相同数的位置，每次排序完返回的是相同数的最左端和最右端的下标。
package niuke.zuoshen;/** * 快速排序(采用荷兰国旗问题，也就是遇到相同大小的数的时候只算一次) * @author tangyuan * * 2019年7月15日 *CopyRight:Copyright(c)2019
*/public class QuickSort { public static void quickSort(int[] arr){ if(arr == null || arr.length < 2) return; quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int l, int r) { if(l < r){ swap(arr, l + (int)(Math.random()*(r - l + 1)),r);//生成随机的分界点解决了当数组有序的时候，时间复杂度为O(N^2) int[] p = partition(arr,l ,r);//每次返回区间的左边界和右边界 quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); } } private static int[] partition(int[] arr, int l, int r) { int less = l - 1; int more = r; while(l < more){ if(arr[l] < arr[r]) swap(arr, ++less, l++); else if(arr[l] > arr[r]) swap(arr, --more, l);//注意这一步，跟右边的换完之后不能前进，而是应该继续跟最小值比较 else { l++; } } swap(arr, more, r); return new int[]{ less + 1, more}; } private static void swap(int[] arr, int i, int r) { int tmp = arr[i]; arr[i] = arr[r]; arr[r] = tmp; }}
注：此外为什么工业上喜欢用快速排序而不喜欢用归并排序呢，因为相同的O（NlogN）,归并排序的常数项系数比较大
采用两个栈，一个实现基本栈功能，一个用来保存当前的栈最小元素,在这个保存当前栈中的最小元素的栈顶一直是当前栈的最小元素。
package niuke.zuoshen;import java.util.Stack;/** * 取得栈中的最小元素值 * @author tangyuan * * 2019年7月15日 *CopyRight:Copyright(c)2019
*/public class GetMinStack { private StackstackData; private Stack stackMin; public GetMinStack() { this.stackData = new Stack<>(); this.stackMin = new Stack<>(); } /** * 压入元素 * @param value */ public void push(int value){ if(stackMin.isEmpty()) { stackMin.push(value); } else if(stackMin.peek() >= value) { stackMin.push(value); } else { stackMin.push(stackMin.peek()); } stackData.push(value); } /** * 弹出元素 * @return */ public int pop(){ if(stackData.isEmpty()) throw new RuntimeException("Your stack is empty"); int value = stackData.pop(); if(!stackMin.isEmpty()) stackMin.pop(); return value; } /** * 获得栈顶元素 * @return */ public int peek(){ return stackData.peek(); } /** * 取得栈中最小元素 * @return */ public int getMin(){ if(stackMin.isEmpty()) throw new RuntimeException("Your stack is empty!"); return stackMin.peek(); }}
使用两个栈（一个压入栈，一个弹出栈）实现一个队列。要注意在弹出元素栈的地方要注意栈的变化，每次压入栈中的元素移动到弹出栈时，要全部移动。当弹出栈中有元素的时候，不能从压入栈中移动元素到弹出栈中。
package niuke.zuoshen;import java.util.Stack;/** * 用两个栈实现队列 * @author tangyuan * * 2019年7月15日 *CopyRight:Copyright(c)2019
*/public class StackConvertToQueue { private StackstackPush; private Stack stackPop; public StackConvertToQueue() { this.stackPush = new Stack<>(); this.stackPop = new Stack<>(); } public void push(int value){ stackPush.push(value); } public int pop(){ if(stackPop.isEmpty() && stackPush.isEmpty()) throw new RuntimeException("queue is empty"); if(stackPop.isEmpty()) while(!stackPush.isEmpty()) stackPop.push(stackPush.pop()); return stackPop.pop(); }}
注：用两个队列实现一个栈，由于本人觉得很傻逼，就不贴代码，就是元素的移动问题。用一个队列一直保持只有一个元素。每次都是弹出这个元素的一个过程。。另外一点就是这两种方法真正在工业上不会用。太傻白甜了。
采用一个辅助栈，第一次遍历的时候将元素压入栈中，再次遍历，每次弹出一个栈中元素，如果不一样，就不是回文串，采用栈的做法不会破坏原单链表的结构。
package niuke.zuoshen;import java.util.Stack;/** * 判断一个单链表是否是回文串 * @author tangyuan * * 2019年7月15日 *CopyRight:Copyright(c)2019
*/public class IsPalindromeList { public static class Node{ private Node next; private int value; public Node(int value) { this.value = value; } } public static boolean isPalindromeList(Node head){ Stackstack = new Stack<>(); Node p = head; while(p != null) { stack.push(p); p = p.next; } p = head; while(!stack.isEmpty()) { Node node = stack.pop(); if(p.value != node.value) return false; p = p.next; } return true; } public static void main(String[] args) { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3);/* Node node4 = new Node(1);*/ Node node5 = new Node(3); Node node6 = new Node(2); Node node7 = new Node(1); node1.next = node2; node2.next = node3; node3.next = node5; /* node4.next = node5;*/ node5.next = node6; node6.next = node7; boolean flag = isPalindromeList(node1); System.out.println(flag); }}
要清楚前序、中序、后序传统的遍历其实都是一次遍历访问节点三次，当在哪一次访问做动作就出现了三种遍历方式。而morris遍历只访问每个节点两次，且利用了每个叶子节点的空指针。
package niuke.zuoshen;import java.util.Stack;/** * 给定一个不带头结点的二叉树，求其前序，中序，后序遍历的结果 * 以及不用辅助空间的morris遍历 * @author tangyuan * * 2019年7月15日 *CopyRight:Copyright(c)2019
*/public class PreInPosTraversal { public static class Node{ private Node left; private Node right; private int value; public Node(int value) { this.value = value; } } /** * 非递归的前序遍历 * @param head */ public static void PreTraverSal(Node head){ if(head == null) return; Stackstack = new Stack<>(); stack.push(head); while(!stack.isEmpty()) { Node node = stack.pop(); System.out.println("value: " + node.value); if(node.right != null) stack.push(node.right); if(node.left != null) stack.push(node.left); } } /** * 中序遍历 * @param head */ public static void InTraversal(Node head){ if(head == null) return; Stack stack = new Stack<>(); Node p =head; while(p != null || !stack.isEmpty()) { if(p != null) { stack.push(p); p = p.left; } else{ p = stack.pop(); System.out.println("value：" + p.value); p = p.right; } } } /** * 后序遍历 * @param head */ public static void orderTraversal(Node head){ if(head == null) return ; Stack stack1 = new Stack<>(); Stack stack2 = new Stack<>(); stack1.push(head); while(!stack1.isEmpty()) { Node node = stack1.pop(); stack2.push(node); if(node.left != null) stack1.push(node.left); if(node.right != null) stack1.push(node.right); } while(!stack2.isEmpty()) { Node node = stack2.pop(); System.out.println("value: " + node.value); } } /** * morris遍历，实现前序和中序比较简单，如何设计到后序遍历比较复杂，涉及到要反转右部分 * @param head */ public static void morrisTraversal(Node head){ if(head == null) return ; Node cur = head; Node morrisRight = null; while(cur != null){ morrisRight = cur.left; if(morrisRight != null) { while(morrisRight.right != null && morrisRight.right != cur) morrisRight = morrisRight.right; if(morrisRight.right == null) { morrisRight.right = cur; System.out.println("value: " + cur.value); cur = cur.left; } else { morrisRight.right = null; cur = cur.right; } } else { //当没有左节点的时候往右走 System.out.println("value: " + cur.value); cur = cur.right; } } } public static void main(String[] args) { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); Node node6 = new Node(6); Node node7 = new Node(7); node1.left = node2; node1.right = node3; node2.left = node4; node2.right = node5; node3.left = node6; node3.right = node7; PreTraverSal(node1); System.out.println("==========="); InTraversal(node1); System.out.println("==========="); orderTraversal(node1); System.out.println("==========="); morrisTraversal(node1); } }
其实就是在做遍历，当在遍历的时候做什么动作，已经规定每个节点的划分和空节点的表示方式。其中反序列化采用先序遍历好做，因为先序遍历是先根节点然后左右孩子。而我们构建一棵二叉树也是有根才有左右孩子，
package niuke.zuoshen;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;/** * 序列化和反序列化二叉树 * @author tangyuan * * 2019年7月16日 *CopyRight:Copyright(c)2019
*/public class SerializeAndReconstructTree { public static class Node{ private Node left; private Node right; private int value; public Node(int value) { this.value = value; } } /** * 前序遍历方式序列化二叉树 * @param head * @return */ public static String serializeByPre(Node head){ if(head == null) return "#!"; String res = head.value + "!"; res += serializeByPre(head.left); res += serializeByPre(head.right); return res; } /** * 中序遍历方式序列化二叉树 * 其中用"!"分割每一个字符 * 用"#"表示空 * @param head * @return */ public static String serializeByIn(Node head){ if(head == null) return "#!"; String res = ""; res += serializeByIn(head.left); res += head.value + "!"; res += serializeByIn(head.right); return res; } /** * 后序遍历方式序列化二叉树 * @param head * @return */ public static String serializeByOrder(Node head){ if(head == null) return "#!"; String res = ""; res += serializeByOrder(head.left); res += serializeByOrder(head.right); res += head.value + "!"; return res; } /** * 前序反序列化二叉树 * @param preStr * @return */ public static Node reconByPreString(String preStr){ String[] values = preStr.split("!"); Queuequeue = new LinkedList<>(); for(int i = 0; i < values.length; i++) { queue.add(values[i]); } return reconTreeByPre(queue); } private static Node reconTreeByPre(Queue queue) { String value = queue.poll();//每次弹出一个元素进行判断 if(value.equals("#"))//为空的话就返回空指针 return null; Node head = null; head.left = reconTreeByPre(queue);//先构建左子树 head = new Node(Integer.valueOf(value)); head.right = reconTreeByPre(queue);//后构建右子树 return head; } /** * 非递归的前序遍历 * @param head */ public static void PreTraverSal(Node head){ if(head == null) return; Stack stack = new Stack<>(); stack.push(head); while(!stack.isEmpty()) { Node node = stack.pop(); System.out.println("value: " + node.value); if(node.right != null) stack.push(node.right); if(node.left != null) stack.push(node.left); } } public static void main(String[] args) { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); Node node6 = new Node(6); Node node7 = new Node(7); node1.left = node2; node1.right = node3; node2.left = node4; node2.right = node5; node3.left = node6; node3.right = node7; String string = serializeByPre(node1); System.out.println(string); System.out.println("=========="); String string2 = serializeByIn(node1); System.out.println(string2); System.out.println("=========="); String string3 = serializeByOrder(node1); System.out.println(string3); System.out.println("=========="); Node node = reconByPreString("1!2!4!#!#!5!#!#!3!6!#!#!7!#!#!"); PreTraverSal(node); }}
首先要清楚完全二叉树的结构，完全二叉树当前节点的左右孩子子树一定有一个是满二叉树结构，然后就可以利用满二叉树的性质。第二点完全二叉树的最左节点的深度一定是最深的，因为完全二叉树的节点排序就是从左到右进行排序的。然后就可以d递归每一部分的完全二叉树计算节点个数
package niuke.zuoshen;/** * 求一颗完全二叉树的节点个数,时间复杂度为(logN)^2 * 采用满二叉树的性质来做，分析左右子树的情况，一定有一边是满二叉树的形状 * @author tangyuan * * 2019年7月12日 *CopyRight:Copyright(c)2019
*/public class CompleteTreeNodeNumber { public static class Node{ private Node left; private Node right; private int value; public Node(int value) { this.value = value; } } public static int nodeNum(Node head){ if(head == null) return 0; return nodeNum(head, 1, mostLeftLevel(head, 1)); } private static int nodeNum(Node head, int level, int high) { if(level == high)//当递归的层数来到最大深度的时候，只有一个节点 return 1; if(mostLeftLevel(head.right, level + 1) == high)//计算右节点的最大深度，是否等于high return (1 << (high - level)) + nodeNum(head.right, level + 1, high); else return (1 << (high - level - 1)) + nodeNum(head.left, level + 1, high); } /** * 求完全二叉树的最大深度，根据完全二叉树的特性，最左节点就是完全二叉树的深度 * @param head * @param level * @return */ private static int mostLeftLevel(Node head, int level) { while(head != null) { level++; head = head.left; } return level - 1; } public static void main(String[] args) { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); Node node6 = new Node(6); Node node7 = new Node(7); Node node8 = new Node(8); Node node9 = new Node(9); Node node10 = new Node(10); Node node11 = new Node(11); Node node12 = new Node(12); node1.left = node2; node1.right = node3; node2.left = node4; node2.right = node5; node3.left = node6; node3.right = node7; node4.left = node8; node4.right = node9; node5.left = node10; node5.right = node11; node6.left = node12; int nodeNum = nodeNum(node1); System.out.println(nodeNum); }}
LRU算法在操作系统中经常使用，比如页面置换等内容，而LRU是当缓存空间达到最大值的时候，最近最少使用的应该被淘汰，而每次操作一个元素的时候，应该被放在最头部。这个结构在Java的LinkedHashMap有实现。本代码就是参考该结构进行设计的，采用HashMap+DoubleLinkedList,其中hashMap具有快速定位元素的功能，List用来维持缓冲区的元素。