算法探秘：全方位解析快速排序
在历年提高组的初赛中，出现了很多与快速排序有关的题目，例如2024年阅读程序第一题的recursion()函数、2023年选择第10题、2020年阅读程序第二题等，而快速排序的思想也是一些利用二分法优化算法的基础，因此本期算法探秘，将带着大家全方位地解析快速排序。
快速排序的基本思路
快速排序是在冒泡排序的基础上使用分治算法进行的优化。冒泡排序中，每一轮的比较都能确定好一个元素的位置，因此最多n-1轮比较才能确定好每一个元素的位置，所以其时间复杂度为O(n^2)。但是如果采用某种分治策略，让每一轮确定更多元素的位置，这就是快速排序的基础。
★ 快速排序的基本思想是，先选取一个元素作为基准数，将小于它的都放到它左边，大于它的都放到它右边，此时，基准数的位置一定是排序好的位置。再对左右两部分进行相同的操作，直到拆分成每部分只有1个数，最终结果即为升序的排序结果。
快速排序是一种不稳定的排序方法，但是其效率非常快，快于多数常用的排序算法。
基础版快速排序的过程
以数组a[10]={5,2,3,9,4,8,7,1,6,4)为例，每次选取区间的第一个元素作为基准数，模拟快速排序的过程：
1、第一轮比较与交换
（1）基准为a[0]=5，剩余数字的左边界i=1,右边界j=9；
（2）先看右边界，a[j] = 4<5，j不变；
（3）再看左边界，a[i] = 2<5，i++;
（4）重复第3步，直到i=3时，a[i] = 9>5，i不用再变；
（5）交换a[i]与a[j]，即9与最后的4，第一次边界移动完成，数组变为{5,2,3,4,4,8,7,1,6,9}，这时候我们发现，两个相同的元素“4”的相对位置发生了变化，因此快速排序是不稳定的排序；
（6）判断i<j,还要继续，重复2~5步；
（7）右边j继续左移，直到j=7时，a[j]=1<5；
（8）左边 i继续右移，直到i=5时，a[i]=8>5;
（9）交换a[i]与a[j]，2次边界移动后，数组变为{5,2,3,4,4,1,7,8,6,9}；
（10）判断i<j，边界移动继续；
（11）右边j继续左移，直到j=5时，a[j]=1<5;
（12）左边i想要继续右移，但是j左移后，i==j，因此i右移强制结束，i=5;
（13）由于i==j,a[i]与a[j]进行了一次无用的交换；
（14）最后将a[0]与a[i]交换，数组变为{1,2,3,4,4,5,7,8,6,9},并记住i=5；
第一轮排序后，a[5]=5已经确定好它的位置了，因此接下来要对两端进行排序；
2、第二轮的比较与交换
（1）a[0]~a[4]与a[6]~a[9]两部分同时进行；
（2）第一部分看到其实已经有序了，因此如果进行比较与交换过后，只会产生a[0]与a[1]~a[4]这样两个子区间。因此，本来就有序的数组，根据上面的规则，又得要判断拆分4次才能确定下来，这时候就需要考虑优化算法了。
（3）第二部分在经过新一轮比较与交换后，可以二分成{6}和{8,9}两个无序序列，并且确定a[7]=7这个元素的位置；
（4）根据上述的分析，样例数组在第一轮快速排序后就可以结束排序了，但是根据快速排序的原理，超过1个元素的区间还要再次进行，会进行多余的比较，因此算法还需要优化。
基础版快速排序部分代码展示
int a[maxn];
void Quick_sort(int l, int r){
if(l>=r) return;
int x=a[l];
int i=l+1, j=r;
while(i<j){
while(i=x){
j--;
}
while(i<j && a[i]<=x){
i++;
}
swap(a[i],a[j]);
}
swap(x,a[i]);
Quick_sort(l,i-1);
Quick_sort(i+1,r);
} 快速排序的多种改良
根据上述对第二轮排序的分析，有多种改良快速排序的方法可以参考：
（1）针对有序或者倒序数组的情况，我们在选取基准数时，改为选择区间中间的数字，这样确保每次递归时总能将数组分为左、右两个区间。由于中间值正好是数组的最大值或最小值的可能性较小，较难出现最差情况；
（2）当二分到每个区间很小时，快速排序的效率就不高了，并且这个时候区间数组基本是有序的了，因此这时候可以改用插入排序，利用好插入排序在最好的情况下时间复杂度为O(n)的特点。
（3）对于已经有序的区间序列，在进行快速排序的比较和交换判断时，不会进行任何一次交换，因此在交换的地方可以做一个计数，如果没有进行交换，那么这个序列肯定是有序的，就不用再递归下去。
快速排序的时空复杂度分析
根据快速排序的思想，理想状态下，第一轮排序确定1个元素的位置，第二轮排序确定2个元素的位置，第三轮排序确定4个元素的位置……以此类推，只需要logn轮排序就能完成，而每轮排序还是遍历整个数组，因此快速排序的平均时间复杂度为O(nlogn)。如果数组是有序或倒序的，那么快速排序无法将数组正确地二分成2个区间，因此时间复杂度会退化成O(n^2)。
快速排序是对数组原地排序的算法，因此数组的空间占用就为n。但是由于算法采用递归实现，递归调用栈内存的空间复杂度平均为O(logn)，最坏情况为O(n)。