要随机在 $[l,r]$ 中选择一个元素作为基准点，否则会退化成 $n^2$
by Reunite @ 2024-02-28 22:05:06
@[_TyT](/user/513596)
快排最差的复杂度是$O(n^2)$的，是会超时的。
by Bob1108 @ 2024-02-28 22:05:30
快排是可以卡掉的，合乎新标准规定的 `std::sort` 是卡不掉的（内省排序）。
选基准的时候选两端会被首当其冲地卡掉，因为构造起来十分简单。
即便是随机基准的快排，如果可以不人道地把你程序的种子都给固定住，也是可以卡掉的，虽然没有人真的可以明目张胆这么干。
by Terrible @ 2024-02-28 22:07:45
@[Reunite](/user/377760) @[Bob1108](/user/981437) @[Terrible](/user/195942) 懂了，蟹蟹
by _TyT @ 2024-02-29 07:04:55
@[Terrible](/user/195942) 我基准选的是l+r>>1，并没有直接选a[l]，但是我将它swap到了a[l],这样也会被卡啊
代码如下：
```
void qp(int l,int r){
if(l>=r)return ;
swap(v[l],v[l+r>>1]);
int pivot=v[l];
int i=l;int j=r+1;
while(i<j){
do i++;while(i<=j&&v[i]<=pivot);
do j--;while(i<=j&&v[j]>=pivot);
if(i<j)swap(v[i],v[j]);
}
swap(v[j],v[l]);
qp(l,j-1);
qp(j+1,r);
}
```
by PerfectLife @ 2024-03-02 12:08:52