目录
1.快速排序的核心思想
2.快速排序的两个重要方法
Hoare法
quickHoare函数（想办法把基准放到数组正确排序好的位置）
代码：
挖坑法
逻辑：
翻译成代码：
3.快速排序的时间/空间复杂度分析
最好情况
最坏情况
总结：
空间复杂度分析
4.基于减少递归的优化方法
三数取中
末尾换用直接插入排序
快速排序的稳定性：
下面都以升序为例进行讲解：
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：
1.在数组中任取一个元素作为基准（基准一般选取最左边的元素），
想办法排列数组，让所有小于基准的元素都放到基准的左边，所有大于基准的元素都放到基准的右边，完成后，基准元素就排列好了。
2.采用分而治之的思想，分别对基准左区间的元素和基准右区间的元素进行1中的操作，从而完成排序。
传入的数组作为唯一的接口，对quickSortHoare方法进行实现：
核心思想中提到了分治，所以大概率我们是要递归定义这个quickHoare方法的：
先不关心quickHoare函数的具体实现和细节，把总体思路捋一遍，以上的代码就是核心思路了，只要把quickHoare实现函数，快速排序就搞定了。
quickHoare函数（想办法把基准放到数组正确排序好的位置）
默认最左边的元素为基准(stand)
left下标和right下标分别指向最左和最右
{1 3 4 5 6 7 9}--》这是排序好的数组，下面看看quickHoare函数，怎么把没排好序的数组中6放到4的位置的：
1.先让right指针做移，直到arr[right]<stand或者左右指针相遇，停下:
2.然后再让left右移，直到arr[left]>stand或者左右指针相遇，停下:
3.到了这里，左右两个指针都停下，arr[left]和arr[right]两个元素进行交换:
4.在重复上述right和left的移动逻辑，直到，left与right相遇（一定会相遇）：
5.遇到上面这个情况实际上就是循环终止条件，直接把arr[left]（当然arr[right]也是可以的）和6进行交换即可：
此时，元素“6”的位置已经排好，在对1 3 4 5和7 9进行分治采用相同的方法即可达到排序目的。
代码：
Hoare方法的整体代码：
不知道小伙伴们有没有这样的困惑：
1、能让left先走，然后right再走吗？
2、为什么arr[left]<=stand 并且arr[right]>=stand ，小于或者等于不可以吗？
首先第一个问题，我们还是用前面那个数组作为样例，进行升序（基准设置成最左端元素）：
让left先走，然后是right,其他逻辑不变：
交换：
left先走:
哦豁，按照这样，6因该放到7的位置，显然是错的
根据1 3 4 5 6 7 9，应该放到4的位置（倒数第三个位置）。
这通过这个例子，证明left先走是不可取的。
注意&总结：
1、选择不同的基准（stand），right和left俩指针移动的先后顺序可能不同！
只要基准选择的不是尾元素，即不是最右端的元素，right先移动。
反之如果基准选取尾元素，也就是最右端的元素，left先移动。
2、不论以那个元素为基准，right指向比stand小的值就停下，left指向比stand大的值就停下，另外两个指针相遇时也得停下。（如果以降序为例，反之亦然）
其次，第二个问题，left>=stand或者right<=stand就停下，以这个数组为例
{ 1 ，1， 1， 1， 1}
如果是这种重复的数组，那么left和right就不可能相遇了，会死循环的。
逻辑：
顾名思义就是挖坑，举个例子：
此时的3，就被挖走了，放到了tmp中（当然这是抽象的理解，实际上3还在数组的原来位置）。
接下来的逻辑就和hoare法差不多，先让right走，但是因为arr[right]=2<3所以，right就不走了，然后把arr[right]“挖走”，填到arr[left]中，然后再让left++：
此时arr[right]形成了新的坑（当然也是抽象理解，实际装的还是2）
我们继续尝试让left前进，但是arr[left]=7>3了，所以left停下，
挖走arr[left]填给arr[right]，然后right往上移动：
循环上面的逻辑：
right移动到1的位置停止：
挖走arr[right]填到arr[left]，然后left往下移动：
此时left==right，退出循环，把tmp填进坑：
翻译成代码：
快速排序的时间复杂度比较特殊，它不是很稳定，最坏情况和最好情况我们都要了解。
假设有N个元素，且恰好定义的基准，排序好的位置在数组的中间：
一共有logN+1层
每一层都有N个元素要被right和left走完，
所以每一层都要执行N此，因此时间复杂度是：
O（fast）=N*(logN+1)=N*logN+N
取最高阶：O（fast）=N*logN
和堆排序的时间复杂度是一样的，不过快速排序实际上要比堆排序快一些，在最好情况下。
什么是最坏情况？
我们可以分离变量，来理解一下，首先对于一个数组进行快速排序，那么他的执行次数至少是N次，因为left=0，right=数组长度-1，即使递归子树，但是每层的子树之和次数也是N
所以每一层的执行次数，永远是N次，那我们只用考虑，啥时候层数是最多的就可以了
我来举个最坏情况的例子：
O（slow）=N^2
这种最坏情况可以说就是一个冒泡排序了
快速排序的时间复杂度是O(n log n)，其中n为待排序数组的长度。快速排序的每次划分操作需要O(n)的时间复杂度，而递归调用的次数为O(log n)，因此总的时间复杂度为O(n log n)。在最坏的情况下，即数组已经有序的情况下，快速排序的时间复杂度为O(n^2)。
实际上快速排序的这三个方法：
定义的变量都是常量级的，是O(1)我们不用管。重要的是，quickHoare方法需要递归，递归要开辟栈帧，所以快速排序的空间复杂度和递归的深度有关。
最优情况时间复杂度为：O(logN)-->每次均等分割
最差情况时间复杂度为：O(N)
如图与时间复杂度最坏情况类似：
想要优化快速排序，从时间复杂度分析中，我们直到，关键就 在于如果减少递归次数。
核心思路就是，选取三个数中中间大的那个数字，作为key（基准），尽量从中间分割数组，从而减少递归次数。
方式也很简单，写一个getMid方法，返回一个靠中间的元素的下标即可：
private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间
int mid=(left+right)/2;
//arr[left] arr[right] arr[mid]三个数组返回中间大的
}
}
依据mid的位置来写，就不容易乱了：
在使用，hoare方法的时候调用getMid方法，来获取基准即可：
private static int partitionHoare(int[] arr,int left,int right){//返回排序好元素的下标 int i=left; int mid=getMid(arr,left,right); swap(arr,mid,left);//把获得的基准和最左侧交换，这样好管理，也好理解 int stand=arr[left];//基准默认是最左边的元素}
先来将两个引子：
第一个，我们先来看一下这颗树：
一共有7个节点，最后一层就占据了4个，是总结点数的一般还多，如果总结点数更大，这个占比可能更大。
第二个，学过直接插入排序，我们都知道，当一个数组趋近于有序，他的排序速度会很快（时间复杂度是O(n)）
学习了上面的直接快速排序，我们都知道，快排需要像二叉树一样递归进行，也会和第一个引子类似，在最后几层，递归次数非常大，而我们使用的又是递归，在测试用例很大的情况下，很可能出现栈溢出。
所以，能不能这样：
在最后几层我们就不递归了，改用，直接插入排序来代替，虽然直接插入排序最坏情况下，时间复杂度是O(O^2)，但是，实际上在最后几层，整个数组，已经被快速排序排列的差不多了，所以这个思路没有问题。
如果直接插入排序还没有学的小伙伴可以看一下这个篇博客，有详细介绍：
只要把_insert方法，放到递归的方法中，设置一个条件来调用即可：
优化后快速排序的整体代码：