目录
前言：
一.算法思想：
二.步骤：
三.算法优化：
四.代码实现：
五.算法评判：
六.小结：
前言：
前两周因为机器人省赛以及后续和大家出去庆祝，学习java数据节后和算法的节奏被打断了。今天就用这一篇博客来重返学习状态，也借此给大家提醒：学习计划中不应该单单包含计划，还应该包含计划中断后怎么办，也就是容错。
接下来我们正式开始快速排序：
一.算法思想：
快速排序采用分治的思想，先找一个基准，比基准小的放到基准左边，比基准大的放基准右边。接下来去递归基准的左边，再去递归基准的右边，使得数组达到有序。
二.步骤：
原数组：int[ ] array = {2, 8, 3, 5, 9, 1, 7, 4, 6};
给定排序的范围begin 和 end 并选定最左侧的2作为基准，让 left 从 begin 开始，right 从 end 开始，先让 right 从右往左找比基准(2)小的数，right找到1，再让left从左往右找比2大的数，left找到8.
让此时 left < right ，让二者指向的数字进行交换。
让 right 继续从右往左找比2小的数，找到1，此时 right 和 left 相等。我们就让基准和left 与 right 相遇的下标所指向的数字进行交换。并把相遇的位置作为我们的 pivot。我么把这个过程叫做一次划分，(partition)，经过一次划分。pivot就来到了排序后的正确的位置，接下来只需要递归pivot的左侧和右侧即可。
接下来去递归 pivot 的左侧，begin 依旧是之前的 begin , end 变成了 pivot - 1 . 此时我们可以发现，begin 和 end 相遇了，说明需要排序的子数组只有一个元素，我们直接 return 即可。
接下来去递归 pivot 的右侧，注意，return 后的 pivot 还是在1下标，那么右侧的 begin 就是pivot + 1，end 就是 之前的 end。
继续一次划分，right 找比3小的，直接找到了left，此时 left 和 right 相等，我们就让left 和 right 相等的下标和基准(3)的下标进行交换，也就是让3和3自己交换。此时我们就会发现让right先动的好处：
right从右往左找比基准小的
left从左往右找比基准大的
我们最后要把相遇点和基准进行交换，就要保证 相遇点 <= pivot
若左边先走，停下来的条件是比基准大，若此时右边追上来，相遇点的值比基准大。
若右边先走，停下来的条件是比基准小，若此时左边追上来，相遇点的值比基准小。
若右侧停下来的时候是一路走到了最左侧，我们就让 left 和自己交换，也没问题。
总结一下就是 ，相遇点的值必须 ≤ pivot，才能和最左边的pivot安全交换。右边先走保证了这一点。
接下来的过程就是一次划分的过程，我们直接用图来表示：
此时再去递归8的左右会发现已然有序，当begin = right ，也就是 子数组只有一个元素时，返回。我们就完成了快速排序。
三.算法优化：
当待排序数组完全有序的时候，我们把left作为基准，会发现每次一趟划分的基准都只有"右子树"，没有"左子树"，就会出现下图的情况：
递归层数为n，每次递归都会开辟新的栈空间，就会造成内存的浪费。我们可以采用三数取中法来解决这个问题。
三数取中法，顾名思义，就是找到left,right,和mid下标的中位数。把这个中位数放到开头，作为基准。这样一来，如果数组是排好序的，我们就可以保证基准的左右子树的节点数是一样的，若数组是无序的，那就和把left作为基准相差不大。
四.代码实现：
class Sort{ public static void quickSort(int[] array,int left,int right){ if(left >= right) return; int oriRight = right; int poivt = left; while(left < right){ while(array[right] >= array[poivt] && left < right){ right--; } while(array[left] <= array[poivt] && left < right){ left++; } if(left < right){ swap(array,left,right); } } swap(array,left,poivt); quickSort(array,poivt,left - 1); quickSort(array,left + 1,oriRight); } //交换 public static void swap(int[] array,int i,int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } } class Test{ public static void main(String[] args){ int[] array = {2,8,3,5,9,1,7,4,6}; Sort.quickSort(array,0,array.length - 1); } }运行结果：
快速排序： 排序前：[2, 8, 3, 5, 9, 1, 7, 4, 6] 排序后：[1, 2, 3, 4, 5, 6, 7, 8, 9]
五.算法评判：
时间复杂度：O(nlog n)
空间复杂度：O(log n)
稳定性：不稳定
六.小结：
自学编程的过程中，卡住并不可怕。可怕的是卡住之后把代码扔一边去逃避。
这次的经历让我明白，“看懂了”和“会写了”之间隔着一条大鸿沟。当你代码卡住时，试着用最朴实的语言把它的执行流程讲给别人（或者写在博客里）听。当你能清晰解释的那一刻，Bug 往往自己就浮出水面了。
