回溯法 剑指Offer.38，回溯法，https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
先把问题码着
个人理解
当改变状态进行递归时，退出该层递归就要对改变的状态还原，也就是回溯，因为接下来的操作是基于上一层的，所以这一层的改变要撤销，到这一层的下个结点时再发生另外的改变。
排序算法时间复杂度
排序算法
时间复杂度（平均）
时间复杂度（最差）
稳定
冒泡排序
O(n2)
O(n2)
稳定
选择排序
O(n2)
O(n2)
不稳定
插入排序
O(n2)
O(n2)
稳定
堆排序
O(nlogn)
O(nlogn)
不稳定
快速排序
O(nlogn)
O(n2)
不稳定
归并排序
O(nlogn)
O(nlogn)
稳定
堆排序建堆时间复杂度O(n)
快速排序 如果快排不堆哨兵优化（随机选取），那么面对一个逆序序列，快排的时间复杂度会达到最差的情况：O(n2)。
215.数组中的第k个最大元素 ：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
这道题朴实无华，就是考察排序的，我就直接使用快排来做，不过我们还需要优化程序，否则效率很低。
随机获取排序哨兵： 普通快排直接把左边界当作哨兵进行左小右大的切割，但效率不高，对于哨兵的选取可以进行优化，如随机获取或三数取中等。
剪枝： 由于本题并没有要求将数组完全排序，所以我们每次完成哨兵位置的确认后，可以将其索引与结果对应索引比较，相等说明当前哨兵就是结果，直接返回。不相等可以比较目标索引与哨兵的位置关系，大于哨兵则只进行右排序，反之只进行左排序，这样我们不会对无用数据进行排序。
快排哨兵确认位置： 其实快排核心就是确定哨兵的位置，并以其为中心，将数组进行左小右大的划分，那么为什么每次左右索引相等时就是哨兵在整个数组中的准确位置呢，下面注释我写的比较清楚了，最后左右索引相遇的位置是小于哨兵的，而现在哨兵是位于左边界的，相遇值已经证实是必定小于哨兵的，所以交换后哨兵就满足了左小右大的条件。
快排一定要先判断右在判断左，为了确保左右索引相遇值小于哨兵。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution public int findKthLargest (int [] nums, int k) int tar = nums.length - k; return quicksort(nums, 0 , nums.length - 1 , tar); } private int quicksort (int [] arr, int l, int r, int tar) random(arr, l, r); int i = l, j = r; while (i < j){ while (i < j && arr[j] >= arr[l]) j--; while (i < j && arr[i] <= arr[l]) i++; swap(arr, i, j); } swap(arr, l, j); if (j == tar) return arr[j]; return j < tar ? quicksort(arr, i + 1 , r, tar) : quicksort(arr, l, i - 1 , tar); } private void swap (int [] arr, int i, int j) int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private void random (int [] arr, int l, int r) Random random = new Random(); int x = l + random.nextInt(r - l + 1 ); swap(arr, l ,x); } }
前中后序遍历的迭代实现 全部都是使用栈模拟，前序和后序比较简单，利用栈先进后出的特性。
前序（力扣144）：根左右，先根入栈然后马上出栈，并记录结点，随后其右孩子、左孩子入栈，此时先进后出左孩子先出栈，然后如果有左右孩子则重复上述操作，最后完成根左右的迭代遍历。
后序（力扣145）：左右根，这里比较取巧，在前序的基础上进行改变，跟入栈出栈，然后如左右孩子，其子结点的左右孩子重复该操作，由于先进后出，则打印顺序是根右左，此时将记录的数组或链表进行颠倒，便可得到左右根的后序遍历。
中序（力扣94）：中序和前后有差异，我们也用栈辅助，先一直遍历左孩子，并将左孩子入栈，若当前结点为空，则当前的遍历指针要回退，我们便把栈顶结点赋予遍历指针，同时栈顶结点出栈并记录。然后有右孩子则走右孩子。一直重复上述操作即可完成左根右的中序。
虽然迭代可以像递归一样，即三种遍历方式使用同一框架，但输出点不同，也就是使用中序遍历的框架，但前序和后序直接想比较好写，就没必要使用相同的结构，反而不好理解。前后是一种类型，后序在前序上反转一次链表即可，中序则是每次左走到头，输出然后走一次右，重复以上操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution public List<Integer> preorderTraversal (TreeNode root) Stack<TreeNode> stack = new Stack<>(); List<Integer> ans = new ArrayList<>(); if (root == null ) return ans; stack.push(root); while (!stack.isEmpty()){ root = stack.pop(); ans.add(root.val); if (root.right != null ) stack.push(root.right); if (root.left != null ) stack.push(root.left); } return ans; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution public List<Integer> inorderTraversal (TreeNode root) Stack<TreeNode> stack = new Stack<>(); List<Integer> ans = new ArrayList<>(); while (root != null || !stack.isEmpty()){ while (root != null ){ stack.push(root); root = root.left; } root = stack.pop(); ans.add(root.val); root = root.right; } return ans; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution public List<Integer> postorderTraversal (TreeNode root) Stack<TreeNode> stack = new Stack<>(); List<Integer> ans = new ArrayList<>(); if (root == null ) return ans; stack.push(root); while (!stack.isEmpty()){ root = stack.pop(); ans.add(root.val); if (root.left != null ) stack.push(root.left); if (root.right != null ) stack.push(root.right); } int l = 0 , r = ans.size() - 1 ; while (l < r){ int num = ans.get(r); ans.set(r, ans.get(l)); ans.set(l, num); r--; l++; } return ans; } }
堆排序 堆类似一个完全二叉树的位置，可以用数组存储，其父与子结点关系如下：parent：i，son：2i + 1、2i + 2。
我们先对无序序列构建大根堆，然后将大元素与末尾置换，此时大元素已排好序，对剩余元素继续维护大根堆，直到排序完毕。
在构建堆里面把堆顶与其子结点的判定反着来，就是维护小顶堆了，最后会逆序输出。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 public class HeapSort public static void heapAdjust (int [] arr, int parent, int length) int child = 2 * parent + 1 ; while (child < length){ if (child + 1 < length && arr[child + 1 ] > arr[child]) { child++; } if (arr[parent] >= arr[child]) { break ; } swap(arr, parent, child); parent = child; child = 2 * parent + 1 ; } } public static void swap (int [] arr, int a, int b) int temp = arr[a]; arr[a] = arr[b]; arr[b]= temp; } public static void main (String[] args) int [] test = new int []{5 , 8 , 9 , 12 , 3 , 4 , 6 , 7 , 8 }; for (int i = test.length / 2 ; i >= 0 ; i--){ heapAdjust(test, i, test.length); } System.out.println(Arrays.toString(test)); for (int i = test.length - 1 ; i >= 0 ; i--){ swap(test, i, 0 ); heapAdjust(test, 0 , i); } System.out.println(Arrays.toString(test)); } }
归并排序 归并是典型的分治思想，先把数组分为小模块，然后先让各个小模块实现部分有序，接着让小模块两两合并排序，先部分有序，后整体有序。注意合并时是对应原数组的相应部分进行排序的，排好序后要把临时排序数组存储到原数组的对应位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public class MergeSort public static void mergeSort (int [] arr, int l, int r) if (l < r){ int mid = (l + r) / 2 ; mergeSort(arr, l, mid); mergeSort(arr, mid + 1 , r); merge(arr, l, mid, r); } } public static void merge (int [] arr, int l, int mid, int r) int [] temp = new int [r - l + 1 ]; int i = l, j = mid + 1 , index = 0 ; while (i <= mid && j <= r){ if (arr[i] <= arr[j]){ temp[index++] = arr[i++]; }else { temp[index++] = arr[j++]; } } while (i <= mid){ temp[index++] = arr[i++]; } while (j <= r){ temp[index++] = arr[j++]; } for (int k = 0 ; k < temp.length; k++){ arr[l + k] = temp[k]; } } public static void main (String[] args) int [] ans = new int []{5 ,9 ,213 ,78 ,6 ,3 ,2 ,1 ,5 ,4 ,7 ,9 ,21 ,321 ,3 ,354 ,54 ,6 ,43 ,13 ,5 }; mergeSort(ans, 0 , ans.length - 1 ); System.out.println(Arrays.toString(ans)); } }
