2021-08-21 · 数据结构 · 2 MIN READ
快速排序
思路
从数组中找一个基准元素，以基准元素将数组分成三部分：
\begin{cases} x, & \text{x<baseEliment} \\ baseEliment \\ y & \text{y>baseEliment} \\ \end{cases}$$ 然后再分别对左右子数组X,Y进行排序。 可以看到，快速排序的核心方法是分区，找到分区位置，之后通过递归的方式分别对其他子数组进行分区。最后完成排序。 ## 框架 ```java void solution(int[] arr, int lo, int hi){ // 递归退出条件 if(lo >= hi) { return; } // 分区 核心部分 int pos = partition(arr, lo, hi); // 递归排序子数组 solution(arr, lo, pos - 1); solution(arr, pos + 1, hi); } ``` ### 说明： 递归必须要有合适的退出条件，否则就会出现堆栈溢出。这里当分区出现最小位置大于等于最大位置时退出递归。 ## 分区 分区的核心思路是：分别从数组左右两边进行扫描，然后找到合适的基准位，将基准元素置换到基准位并返回基准位。 ```java void patition(int[] arr, int lo, int hi) { // 定义扫描指针 int l = lo; int r = hi + 1; // 确定基准位元素 int seed = arr[lo]; // 开始扫描 while(true) { // 从左向右 while(arr[++l] <= seed) { // 达到最大搜索区间，退出 if(l == hi) { break; } } // 从右向左 while(arr[--r] >= seed) { // 达到最小搜索区间，退出 if(r == lo) { break; } } // 找到了基准位置r，退出循环 if(r <= l) { break; } // 尚未找到基准位置，需要后续继续扫描，当前左右指针位置数据进行交换 switch(arr, r, l); } // 将基准位元素放置到争取的位置 switch(arr, lo, r); // 返回基准位 return r; } ``` ### 说明： 这段逻辑中比较关键的点是：为啥最外层的扫描循环退出条件是 r <= l。 我们先看r < l的情况 通过基准位元素和分区规则我们可以知道，那就是左右扫描结束时必须满足下面的条件 $$patition(n) = \begin{cases} a[x], &x<l;l<=hi;a[x]<baseEliment \\ a[y], &y>r;l>=lo;a[y]>baseEliment \\ \end{cases}$$ 根据上面公式，我们可以推导出下面结论: ```java ### 遍历左指针可能情况 case l == lo //这种情况不可能出现，因为左指针的起始扫描位置就是lo+1 case lo < l < hi //左指针在中间位置 此时一定满足 a[r]>base && a[i{i < r}] <= base case l > r // 这时，说明数字排序比较乱，a[l]<base && a[i{i>l}] >= base // 在r和l之间存在倒序的情况 // 这时直接对r,l两个元素进行交换 case l < r // 这里出现了一个临界点j，临界点左边的元素都小于base 右边的元素都大于base // 那么，这时只需要把临界点前面的元素与base交换即可。 case l == r // 由上面公式可知，达到临界点j时，l还会再扫描一次，变更j+1 // r也会扫描一次，变成j-1 所以r和j不会在临界点相遇 case l==hi case r == hi // 当数组中原有元素都比基准位小时，左指针会达到最大搜索区间，同时，右指针也会停在最大搜索区间 case r < hi // 右上可知，这种情况不存在 ``` **结论：当且仅当r <= l时，函数找到临界点r;** r < l时：临界点在数组中间 r = l时：临界点在数组最右端 ## 复杂度 ### 空间复杂度 应该没有使用额外空间，所有操作都在数组上进行，所以空间复杂度为：O(n) ### 时间复杂度 **最好情况：** 由于快排本质上是二叉树的前序遍历，理想情况下每一层的遍历次数如下  那么总共的遍历次数为：n*树高 由等比数列求和公式我们可以计算树高为：h(tree) ≈ log(n) $$S(n) = \frac{a(1-q^n)}{1-q}\\所以，在理想情况下,快排的时间复杂度为O(N*logN)
最差情况：
如上图所示，数组每次分区基准位都在子数组的第一个元素。这样左子树每次不遍历，右子数组每次遍历n-depth(tree)
这种极不平衡二叉树高度等于数组元素个数n。那么最差情况时间复杂度O(n)≈N*N