上面的代码也很容易理解，其实就是一个“填坑”的过程，第一个“坑”挖在每次排序的第一个位置arr[low]，从序列后面往前找第一个比pivot小的数来把这个“坑”填上，这时候的“坑”就变成了当前的arr[high]，然后再从序列前面往后用第一个比pivot大的数把刚才的“坑”填上，如此往复，始终有一个“坑”需要我们填上，直到最后一个“坑”出现，这个“坑”使用一开始的pivot填上就可以了，而这个“坑”的位置也就是pivot该填上的正确位置，我们再把这个位置返回，就可以把当前序列分成两个部分再依次这样操作最终就达到排序的目的了，不得不说这样的思想挺神奇的；
算法优化上面这个快速排序算法可以说是最基本的快速排序，因为它并没有考虑任何输入数据。但是，我们很容易发现这个算法的缺陷：这就是在我们输入数据基本有序甚至完全有序的时候，这算法退化为冒泡排序，不再是O(n㏒n)，而是O(n^2)了。
究其根源，在于我们的代码实现中，每次只从数组第一个开始取。如果我们采用“三者取中”，即 arr[low], arr[high], arr[(low+high)/2] 三者的中值作为枢轴记录，则可以大大提高快速排序在最坏情况下的性能。但是，我们仍然无法将它在数组有序情形下的性能提高到O(n)。还有一些方法可以不同程度地提高快速排序在最坏情况下的时间性能。
此外，快速排序需要一个递归栈，通常情况下这个栈不会很深，为log(n)级别。但是，如果每次划分的两个数组长度严重失衡，则为最坏情况，栈的深度将增加到O(n)。此时，由栈空间带来的空间复杂度不可忽略。如果加上额外变量的开销，这里甚至可能达到恐怖的O(n^2)空间复杂度。所以，快速排序的最差空间复杂度不是一个定值，甚至可能不在一个级别。
为了解决这个问题，我们可以在每次划分后比较两端的长度，并先对短的序列进行排序（目的是先结束这些栈以释放空间），可以将最大深度降回到O(㏒n)级别。
关于优化的话，了解一个大概的思路就可以了，那在这里稍微总结一下：
①三数取中作为枢轴记录；
②当待排序序列的长度分割到一定大小之后，使用插入排序；
③在一次分割结束后，可以把与pivot相等的元素聚在一起，继续下次分割时，不用再对与pivot相等的元素分割；
④优化递归操作；
参考文章：
想要了解的更多的童鞋可以戳这里：https://blog.csdn.net/insistGoGo/article/details/7785038
二叉树也是一个容易提及的概念和写算法的问题，特别是它的几种递归遍历和非递归遍历，都是基础且常考的点，那在这里就稍微整理整理吧...
二叉树的几种递归遍历前序、中序、后序遍历都是非常基础且容易的遍历方法，重点还是在后面的中序和后续的非递归遍历上，当然还有层序遍历，所以这里不多说，直接给代码；
前序遍历递归实现 public void preOrderTraverse1(TreeNode root) { if (root != null) { System.out.print(root.val + " "); preOrderTraverse1(root.left); preOrderTraverse1(root.right); } } 中序遍历递归实现 public void inOrderTraverse1(TreeNode root) { if (root != null) { preOrderTraverse1(root.left); System.out.print(root.val + " "); preOrderTraverse1(root.right); } } 后序遍历递归实现 public void postOrderTraverse1(TreeNode root) { if (root != null) { preOrderTraverse1(root.left); preOrderTraverse1(root.right); System.out.print(root.val + " "); } }前面三种遍历，也就是输出结点数据的位置不同而已，所以很容易，但是如果手写，建议问清楚面试官要求，是在遍历时直接输出还是需要函数返回一个List集合，然后注意写测试用例代码！
二叉树的几种非递归遍历 ★★层序遍历★★层序遍历我们只需要增加使用一个队列即可，看代码很容易理解：
public void levelTraverse(TreeNode root) { if (root == null) { return; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); System.out.print(node.val + " "); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } 前序遍历非递归实现 public void preOrderTraverse2(TreeNode root) { if (root == null) { return; } LinkedList<TreeNode> stack = new LinkedList<>(); TreeNode pNode = root; while (pNode != null || !stack.isEmpty()) { if (pNode != null) { System.out.print(pNode.val + " "); stack.push(pNode); pNode = pNode.left; } else { //pNode == null && !stack.isEmpty() TreeNode node = stack.pop(); pNode = node.right; } } } ★★中序遍历非递归实现★★ /** * 非递归中序遍历二叉树 * * @param root 二叉树根节点 * @return 中序遍历结果集 */ public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); ArrayDeque<TreeNode> stack = new ArrayDeque<>(); while (root != null || !stack.isEmpty()) { while (root != null) { stack.addFirst(root); root = root.left; } root = stack.removeFirst(); list.add(root.val); root = root.right; } return list; } ★★后续遍历非递归实现★★ /** * 二叉树的后序遍历 * * @param root 二叉树根节点 * @return 后序遍历结果集 */ public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode pre = null; while (!stack.isEmpty() || root != null) { while (root != null) { stack.push(root); root = root.left; } root = stack.peek(); // i ：判断如果右子树不为空且不为 if (root.right != null && root.right != pre) { root = root.right; } else { root = stack.pop(); list.add(root.val); pre = root; root = null; } } return list; }如果比较难以理解的话，可以自己尝试着跟跟 Debug 然后看看过程；
二叉树相关其他算法题另外的话还有一些比较常见的关于树的算法，在文章的末尾，这里就不再赘述了：
链接：https://www.jianshu.com/p/4ef1f50d45b5
Part 4.其他重要算法除了上面 3 Part 比较重要的点之外，还有一些其他的算法也是经常考到的，下面我们来说；
1.反转链表