目录
quickHoare函数（想办法把基准放到数组正确排序好的位置）
下面都以升序为例进行讲解：
1.快速排序的核心思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：
1.在数组中任取一个元素作为基准（基准一般选取最左边的元素），
想办法排列数组，让所有小于基准的元素都放到基准的左边，所有大于基准的元素都放到基准的右边，完成后，基准元素就排列好了。
2.采用分而治之的思想，分别对基准左区间的元素和基准右区间的元素进行1中的操作，从而完成排序。
2.快速排序的两个重要方法
Hoare法
传入的数组作为唯一的接口，对quickSortHoare方法进行实现：
public static void quickSortHoare(int[] arr){
quickHoare(arr,0,arr.length-1);
}核心思想中提到了分治，所以大概率我们是要递归定义这个quickHoare方法的：
private static void quickHoare(int[] arr,int left,int right){
if(left>=right)return;//已经没有排序区间了，直接返回即可
//下面这个partionHoare方法可以把基准放到排序好的位置，然后返回基准排好后的下标位置
int mid=partitonHoare(arr,left,right);//left和right一定是合法有效的
quickHoare(arr,left,mid-1);//递归基准左侧区间
quickHoare(arr,mid+1,right);//递归基准右侧区间
}先不关心quickHoare函数的具体实现和细节，把总体思路捋一遍，以上的代码就是核心思路了，只要把quickHoare实现函数，快速排序就搞定了。
quickHoare函数（想办法把基准放到数组正确排序好的位置）
默认最左边的元素为基准(stand)
left下标和right下标分别指向最左和最右
{1 3 4 5 6 7 9}--》这是排序好的数组，下面看看quickHoare函数，怎么把没排好序的数组中6放到4的位置的：
1.先让right往前走，只要arr[right]>=stand，right就减减:
2.然后再让left往下走，只要arr[left]<=3，left就加加:
3.到了这里，right和left都不能走了，所以接下来arr[left]和arr[right]两个元素进行交换:
4.在重复上述right和left的移动逻辑，直到，left与right相遇（一定会相遇）：
5.遇到上面这个情况实际上就是循环终止条件，直接把arr[left]（当然arr[right]也是可以的）和6进行交换即可：
此时，元素“6”的位置已经排好，在对1 3 4 5和7 9进行分治采用相同的方法即可达到排序目的。
代码：
private static int partitonHoare(int[] arr,int left,int right){//返回排序好元素的下标
int i=left;
int stand=arr[left];//基准默认是最左边的元素
while(left<right){//此条件防止下标越界
//先右边下标走
while(left<right&&arr[right]>=stand){
right--;
}
while(left<right&&arr[left]<=stand){
left++;
}
//程序到达这里时：arr[right]<stand 而arr[left]>stand
swap(arr,right,left); //交换arr[right]和arr[left]
}
//当程序到达这里，right==left了，此时这两个下标所指的位置，就是arr[i]有序时，因该在的位置
swap(arr,i,left);
return left;//返回right也是一样的
}
Hoare方法的整体代码：
class TestSort{
private static void swap(int[] arr,int a,int b){
int t=2;
t=arr[a];
arr[a]=arr[b];
arr[b]=t;
}
public static void quickSortHoare(int[] arr){
quickHoare(arr,0,arr.length-1);
}
private static void quickHoare(int[] arr,int left,int right){
if(left>=right)return;//已经没有排序区间了，直接返回即可
//下面这个partionHoare方法可以把基准放到排序好的位置，然后返回基准排好后的下标位置
int mid=partitonHoare(arr,left,right);//left和right一定是合法有效的
quickHoare(arr,left,mid-1);//递归基准左侧区间
quickHoare(arr,mid+1,right);//递归基准右侧区间
}
private static int partitonHoare(int[] arr,int left,int right){//返回排序好元素的下标
int i=left;
int stand=arr[left];//基准默认是最左边的元素
while(left<right){
//先右边下标走
while(left<right&&arr[right]>=stand){
right--;
}
while(left<right&&arr[left]<=stand){
left++;
}
//程序到达这里时：arr[right]<stand 而arr[left]>stand
swap(arr,right,left); //交换arr[right]和arr[left]
}
//当程序到达这里，right==left了，此时这两个下标所指的位置，就是arr[i]有序时，因该在的位置
swap(arr,i,left);
return left;//返回right也是一样的
}
不知道小伙伴们有没有这样的困惑：
1、能让left先走，然后right再走吗？
2、为什么arr[left]<=stand arr[right]>=stand 小于或者等于不可以吗？
首先第一个问题，我们：还是用前面那个数组作为样例
让left先走，然后是right,其他逻辑不变：
交换：
left先走:
哦豁，按照这样，6因该放到7的位置，显然是错的
根据1 3 4 5 6 7 9，因该放到4的位置（倒数第三个位置）。
这就是为什么要让right先走，然后left再走的原因的原因。
其次，第二个问题，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填进坑：
如图，3已经在升序的正确位置了。
翻译成代码：
private static int partitionPit(int[] arr,int left,int right){//左右，都是有效的闭区间下标
int tmp=arr[left];//先挖一个坑(在left的位置)，把土放进tmp
while(left<right){
while(left<right&&arr[right]>=tmp){
right--;
}
arr[left]=arr[right];//填坑，然后arr[right]成了新的坑
while(left<right&&arr[left]<=tmp){
left++;
}
arr[right]=arr[left];//填坑，在挖坑
}
arr[left]=tmp;//把最后一个坑填上
return left;
}3.快速排序的时间复杂度分析
快速排序的时间复杂度比较特殊，它不是很稳定，最坏情况和最好情况我们都要了解。
最好情况
假设有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次，那我们只用考虑，啥时候层数是最多的就可以了
我来举个最坏情况的例子：
像这种基准永远都在最最左侧的情况下，是没有右树的，程序会递归N次，每次left，right走的总次数是一个公差为-1，首项为N的等比数列，所以时间复杂度就是有N项，首项为N，公差为-1的等差数列，自然时间复杂度是：
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)
如图与时间复杂度最坏情况类似：
4.基于减少递归的优化方法
想要优化快速排序，从时间复杂度分析中，我们直到，关键就 在于如果减少递归次数。
三数取中
核心思路就是，选取三个数中中间大的那个数字，作为key（基准），尽量从中间分割数组，从而减少递归次数。
方式也很简单，写一个getMid方法，返回一个靠中间的元素的下标即可：
private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间
int mid=(left+right)/2;
//arr[left] arr[right] arr[mid]三个数组返回中间大的
}
}
实际上就只有三大种情况：
依据mid的位置来写，就不容易乱了：
private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间
int mid=(left+right)/2;
if(arr[left]<arr[right]){
if(arr[left]>arr[mid])return left;
else if(arr[right]<arr[mid])return right;
else return mid;//mid不小于left，也不大于right，那么就返回mid啊
}else{//下面的写法逻辑和上面是一模一样的(arr[left])>arr[right]的情况)--》如果有有元素相同，返回任意一个，所以可以不关心“=”的情况
if(arr[mid]<arr[right])return right;
else if(arr[mid]>arr[left])return left;
else return 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)，但是，实际上在最后几层，整个数组，已经被快速排序排列的差不多了，所以这个思路没有问题。
private static void _insert(int[] arr,int left,int right){
//把直接插入排序中，对0，和数组长度length的限制改成left,right的就可以了
for (int i = left+1; i <=right ; i++) {
int tmp=arr[i];
int j=i-1;
for ( ; j >=left ; j--) {
if(arr[j]>tmp)arr[j+1]=arr[j];//一直和tmp比较啊啊啊啊啊，只要tmp小，就一直往前找到合适为止
else break;//如果arr[j]<=arr[j+1]，那么数组已经“有序了”
}
arr[j+1]=tmp;//填好以后一个元素
}
}如果直接插入排序还没有学的小伙伴可以看一下这个篇博客，有详细介绍：直接插入排序与希尔排序的详解及对比
只要把_insert方法，放到递归的方法中，设置一个条件来调用即可：
private static void quickHoare(int[] arr,int left,int right){
if(left>=right)return;//已经没有排序区间了，直接返回即可
if(right-left<6){//如果递归区间小于某一个值，就直接插入排序，对于值的设置，没有严格要求，不要太大就可以
_insert(arr,left,right);
return;//记得返回，不然还会继续进行下面的程序，去递归
}
//下面代码，和之前一样，就不展示了
。。。。。。
}优化后快速排序的整体代码：
class TestSort{
private static void swap(int[] arr,int a,int b){
int t=2;
t=arr[a];
arr[a]=arr[b];
arr[b]=t;
}
public static void quickSortHoare(int[] arr){
quickHoare(arr,0,arr.length-1);
}
private static void quickHoare(int[] arr,int left,int right){
if(left>=right)return;//已经没有排序区间了，直接返回即可
if(right-left<6){
_insert(arr,left,right);
return;//记得返回，不然还会继续进行下面的程序，去递归
}
//下面这个partionHoare方法可以把基准放到排序好的位置，然后返回基准排好后的下标位置
int mid=partitionHoare(arr,left,right);//left和right一定是合法有效的
quickHoare(arr,left,mid-1);//递归基准左侧区间
quickHoare(arr,mid+1,right);//递归基准右侧区间
}
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];//基准默认是最左边的元素
while(left<right){
//先右边下标走
while(left<right&&arr[right]>=stand){
right--;
}
while(left<right&&arr[left]<=stand){
left++;
}
//程序到达这里时：arr[right]<stand 而arr[left]>stand
swap(arr,right,left); //交换arr[right]和arr[left]
}
//当程序到达这里，right==left了，此时这两个下标所指的位置，就是arr[i]有序时，因该在的位置
swap(arr,i,left);
return left;//返回right也是一样的
}
private static int partitionPit(int[] arr,int left,int right){//左右，都是有效的闭区间下标
int tmp=arr[left];//先挖一个坑(在left的位置)，把土放进tmp
while(left<right){
while(left<right&&arr[right]>=tmp){
right--;
}
arr[left]=arr[right];//填坑，然后arr[right]成了新的坑
while(left<right&&arr[left]<=tmp){
left++;
}
arr[right]=arr[left];//填坑，在挖坑
}
arr[left]=tmp;//把最后一个坑填上
return left;
}
private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间
int mid=(left+right)/2;
if(arr[left]<arr[right]){
if(arr[left]>arr[mid])return left;
else if(arr[right]<arr[mid])return right;
else return mid;//mid不小于left，也不大于right，那么就返回mid啊
}else{//下面的写法逻辑和上面是一模一样的(arr[left])>arr[right]的情况)--》如果有有元素相同，返回任意一个，所以可以不关心“=”的情况
if(arr[mid]<arr[right])return right;
else if(arr[mid]>arr[left])return left;
else return mid;
}
}
private static void _insert(int[] arr,int left,int right){
//把直接插入排序中，对0，和数组长度length的限制改成left,right的就可以了
for (int i = left+1; i <=right ; i++) {
int tmp=arr[i];
int j=i-1;
for ( ; j >=left ; j--) {
if(arr[j]>tmp)arr[j+1]=arr[j];//一直和tmp比较啊啊啊啊啊，只要tmp小，就一直往前找到合适为止
else break;//如果arr[j]<=arr[j+1]，那么数组已经“有序了”
}
arr[j+1]=tmp;//填好以后一个元素
}
}
}快速排序的稳定性：
不稳定
