前言

这篇文章主要介绍在常见的排序算法中综合性能最高的算法——快速排序

快速排序

🍅1.思路梳理与确定基准位置

思想：
实现快排的思想就是在待排序列中找一个基准值，让待排序列中比基准值小的元素放在基准值左边，比基准值大的元素放在基准值右边，这样就确定了基准值在待排序列中的位置，再让基准值左侧和右侧的区间分别进行相同的操作，直到区间中只剩下一个元素时，待排序列中的所有元素就有序了。

简单实现方法都是先让数组第一个元素作为基准值，然后通过数组中其他元素与该值的比较来确定该基准值应该在的位置。
将区间按照基准值划分为左右两半部分的常见方式有三种：

• 挖坑法
• Hoare法
• 前后指针法

挖坑法实现思路：
1.选取数组中第一个元素作为基准值，存储该元素并将该位置腾出坑位。
2.设立两个指针分别位于数组的始末，先让后边的指针往前走，遇到比基准值小的元素，就让该元素移至坑位。
3.让前边的指针往前走，遇到比基准值大的元素再填入新坑位
4.前后指针交替进行相同的操作，直到两个指针相遇时，将之前存储的元素至于该坑位，区间划分完毕。

代码实现：

	private static int partitionHole(int[] array,int start,int end) {
        int key=array[start];
        while (start<end) {
            while (start<end&&array[end]>=key) {
                end--;
            }
            array[start]=array[end];
            while (start<end&&array[start]<=key) {
                start++;
            }
            array[end]=array[start];
        }
        array[start]=key;
        return start;
    }

Hoare法实现思路：
1.选取数组中第一个元素作为基准值，设立两个指针分别位于数组的始末。
2.让后指针先走，遇到比基准值小的元素停下；前指针后走，遇到比基准值大的元素停下，前后两指针所在位置元素交换。
3.交换完毕后继续相同操作，直至两指针相遇，让区间第一个元素与相遇位置元素互换。

代码实现：

    private static int partitionHoare(int[] array,int start,int end) {
        int i=start;//先存储好start下标，用于最后的交换
        int key=array[start];
        while (start<end) {
        	//为什么取等号？为什么后指针先走？在下边分析中解释
            while (start<end&&array[end]>=key) {
                end--;
            }
            while (start<end&&array[start]<=key) {
                start++;
            }
            swap(array,start,end);
        }
        swap(array,start,i);
        return start;
    }

细节问题分析：
1.为什么取等号？
若遇到像下图这样的情况，将会进入死循环，所以必须加上等号

2.为什么让后指针先走？
让后指针先走，前指针后走，重复这样的操作直到两指针相遇时，能保证相遇位置元素一定比区间起始位置元素小，才能让两者交换后保证基准值前边的元素都小于基准值，后边的元素都大于基准值。

前后指针法实现思路：
1.选取区间第一个元素作为基准值，第一个元素先不动
2.设立快慢指针从前往后遍历，遇到比基准值大的元素，快指针走慢指针不走，再次符合条件时进行交换
3.最后快指针走完后，让区间起始位置元素与慢指针位置元素交换

代码实现：

	public static int partition(int[] array,int start,int end) {
        int prev=start;
        int cur=start+1;
        while (cur<=end) {
            if(array[cur]<array[start]&&array[++prev]!=array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,start);
        return prev;
    }

🍅2.实现并优化

在1中，我们已经确定了基准位置，现在我们可以通过1中思路的梳理来简单实现快排（以Hoare法为例）
简单实现：

 	private static void quick(int[] array,int left,int right) {
 		//在升序或降序的极端情况下，会出现left>right的情况
        if(left>=right) {
            return;
        }
        int pivot=partitionHoare(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

分析思路与代码可以发现，通过递归实现的快排，如果在理想状态下，每次的基准值都位于区间的正中间，就会构成一棵完全二叉树（如下图），分析上边的代码可以发现，快排方法的时间复杂度理想状态为O(N* $log_2N$),空间复杂度为递归深度O（ $log_2N$）;

quick(array,left,pivot-1); 求pivot的时间复杂度为O(N)，递归深度如果为完全二叉树就是 $log_2N$.

但如果待排序列为升序或者降序时，如果取区间起始位置或结束位置为基准值进行递归，将会得到的是一课只有左孩子的树或者只有右孩子的树，其深度为N，这样的时间复杂度将会变为O（N^2）,空间复杂度为O(N).（如果真的是这样的极端情况，递归的深度太深，如果数据量较大将会栈溢出）

所以我们可以通过调整基准值的选取方式来优化递归，采用的方法为三数取中法选取基准值
，就是通过选取区间两个边界和中间位置三个元素的中数作为基准值的方式，才会减少递归的深度。

	private static int midNumIndex(int[] array,int left,int right) {
        int mid = (left+right) / 2 ;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]){
                return left;
            }else {
                return mid;
            }
        }
    }

再有就是当递归深度足够深时，区间内的元素基本已经趋于有序，这时可以在小区间改用直接插入排序的方式再次减少递归深度。

此时的直接插入需要稍作改动：

	private static void insertSort(int[] array,int start,int end) {
        for (int i = start+1; i <=end ; i++) {
            int tmp=array[i];
            int j=i-1;
            for (; j >=start ; j--) {
                if(array[j]>tmp) {
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

最后优化后的代码：

	public static void swap(int[] array,int i,int j) {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
	}

   private static void quick(int[] array,int left,int right) {
        if(left>=right) {
            return;
        }
        //小区间使用直接插入排序： 主要 优化了递归的深度
        if(right-left+1<=7) {
            insertSort(array, left, right);
            return;
        }
        //三数取中：解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*logn
        int index = midNumIndex(array,left,right);
        swap(array,left,index);
        
        int pivot=partitionHoare(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

通过优化，时间复杂度就可以达到O(N* $log_2N$),空间复杂度就是递归的深度O( $log_2N$)

🍅3.非递归实现

通过利用栈来非递归的实现排序
思路：
先将基准值放在指定位置，然后分别入栈基准值左区间的边界角标和基准值右区间的边界角标（当区间元素只剩1时不入栈），弹出两个栈顶元素分别作为新区间的始末位置再找基准，重复相同操作直至所有元素完成排序。

代码实现：

	public static void quickSort2(int[] array) {
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int index=midNumIndex(array,left,right);
        swap(array,left,index);
        int pivot=partitionHole(array,left,right);
        if(pivot>left+1) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if (pivot<right-1) {
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.empty()) {
            right=stack.pop();
            left=stack.pop();
            index=midNumIndex(array,left,right);
            swap(array,left,index);
            pivot=partitionHole(array,left,index);
            if(pivot>left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot<right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

🍅4.特性总结

• 经过优化后的快速排序，综合性能和使用场景都是比较好的，所以才叫做快速排序
• 时间复杂度（优化后） O(N* $log_2N$)
• 空间复杂度（优化后） O( $log_2N$)
• 稳定性：不稳定

最后的话
==总结不易，希望uu们不要吝啬你们的👍哟(＾Ｕ＾)ノ~ＹＯ！！如有问题，欢迎评论区批评指正😁==