快排的基准问题

起因很简单，就是在acWing里做一道快排模板，但是提交了代码就是TLE。于是好奇心大发仔细对比了一下自己写的和课程中展示的代码。

以下是1.0版：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int q[N];
void quick_sort(int q[],int l,int r) {
    if (l >= r) return;
    int x=q[l],i=l-1,j=r+1;
    while(i<j) {
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,i-1);
    quick_sort(q,i,r);
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&q[i]);
    }
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++) {
        printf("%d ", q[i]);
    }
    return 0;
}

大不解，遂问ds问题所在。ds回答如下：

TLE 的原因：
最坏时间复杂度 O(n²)

你的代码选择 q[l]（第一个元素）作为 pivot，如果输入是已排序或接近排序的数组，会导致递归深度变成 O(n)，时间复杂度退化为 O(n²)。

咱们不妨举一个简单的例子看看，为什么左边界会在一定情况下超时

如果数组已经有序（或逆序）：
比如 [1, 2, 3, 4, 5]，每次选 pivot = 第一个元素：
第一次：pivot = 1 → 左边 []，右边 [2, 3, 4, 5]（没分割）。
第二次：pivot = 2 → 左边 []，右边 [3, 4, 5]（又没分割）。
...
每次只减少 1 个元素，递归深度变成 N 层，每层处理 N 个元素 → O(N²)！

所以，在快速排序的时候，我们通常有四种选择基准的方法：左端，右端，中间位置，随机位置。

更改中间位置为基准后成功ac，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int q[N];
void quick_sort(int q[],int l,int r) {
    if (l >= r) return;
    int x=q[(l+r+1)/2],i=l-1,j=r+1;
    while(i<j) {
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,i-1);
    quick_sort(q,i,r);
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&q[i]);
    }
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++) {
        printf("%d ", q[i]);
    }
    return 0;
}

最后，ds给出了一个很幽默的解决方法：随机位置

(但是总觉得有点~~不太靠谱啊