荷兰国旗问题：给定一个整数数组，给定一个值K，这个值在原数组中一定存在，要求把数组中小于K的元素放到数组的左边，大于K的元素放到数组的右边，等于K的元素放到数组的中间，最终返回一个整数数组，其中只有两个值，分别是等于K的数组部分的左右两个下标值
public static int[] sort(int[] arr) { partiton(arr, 0, arr.length - 1); return arr; } public static int[] partiton(int[] arr, int left, int right) { int less = left - 1; int more = right + 1; int pNum = arr[right]; while (left < more) { if (arr[left] < pNum) { MyUtils.swap(arr, ++less, left++); } else if (arr[left] > pNum) { MyUtils.swap(arr, --more, left); } else { left++; } } return new int[]{less, more}; }
快速排序：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作，递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
// 基于荷兰国旗问题的快排 public static int[] sort(int[] arr) { sort(arr, 0, arr.length - 1); return arr; } public static void sort(int[] arr, int left, int right) { if (left < right) { int[] pIndexs = DutchFlag.partiton(arr, left, right); sort(arr, left, pIndexs[0]); sort(arr, pIndexs[1], right); } }
堆排序：先建立大根堆，然后不停做heapify，也就是把未有序的最后一位和堆首互换，然后调整堆结构
public static int[] sort(int[] arr) { int len = arr.length; buildBigHeap(arr, len); while (len > 0) { MyUtils.swap(arr, 0, --len); heapify(arr, 0, len); } return arr; } // 建立大根堆 public static void buildBigHeap(int[] arr, int len) { for (int index = 0; index < arr.length; index++) { while (arr[index] > arr[(index - 1) / 2]) { MyUtils.swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } } // 调整堆 private static void heapify(int[] arr, int currRoot, int len) { int left = currRoot * 2 + 1; int right = currRoot * 2 + 2; while (left < len) { int largest = right < len && arr[left] < arr[right] ? right : left; largest = arr[largest] > arr[currRoot] ? largest : currRoot; if (largest == currRoot) { break; } MyUtils.swap(arr, currRoot, largest); currRoot = largest; left = currRoot * 2 + 1; right = currRoot * 2 + 2; } } 二叉树前序 中序 后续 层级遍历
public static void pre(TreeNode root) { if (root != null) { Stack<TreeNode> stack = new Stack<>(); stack.push(root); // 先进右再进左 while (!stack.isEmpty()) { root = stack.pop(); System.out.print(root.val + " -> "); if (root.right != null) { stack.push(root.right); } if (root.left != null) { stack.push(root.left); } } } System.out.println(); } public static void preReur(TreeNode root) { if (root == null) { return; } System.out.print(root.val + " -> "); preReur(root.left); preReur(root.right); } public static void mid(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); // 左走到头了开始弹，然后去右 while (root != null || !stack.isEmpty()) { if (root != null) { stack.push(root); root = root.left; } else { root = stack.pop(); System.out.print(root.val + " -> "); root = root.right; } } System.out.println(); } public static void midReur(TreeNode root) { if (root == null) { return; } midReur(root.left); System.out.print(root.val + " -> "); midReur(root.right); } public static void post(TreeNode root) { // 把线序遍历反过来，得到前右左，然后再反过来变成左右前 if (root != null) { Stack<TreeNode> stackStack = new Stack<>(); Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { root = stack.pop(); stackStack.push(root); if (root.left != null) { stack.push(root.left); } if (root.right != null) { stack.push(root.right); } } while (!stackStack.isEmpty()) { System.out.print(stackStack.pop().val + " -> "); } } System.out.println(); } public static void postReur(TreeNode root) { if (root == null) { return; } postReur(root.left); postReur(root.right); System.out.print(root.val + " -> "); } public static void level(TreeNode root) { if (root == null) { return; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); TreeNode curr = null; while (!queue.isEmpty()) { curr = queue.pop(); System.out.print(curr.val + " -> "); if (curr.left != null) { queue.add(curr.left); } if (curr.right != null) { queue.add(curr.right); } } } 算法验证对数器准备样本随机生成器
准备一个绝对正确但是复杂度不好的算法
将待验证算法和绝对正确算法压测，比较
主定理与递归时间复杂度的计算