为什么用快排会出现tle，怎么解决

hhy20080531 @ 2021-11-07 14:41:11

#include<iostream>
#include <algorithm>
using namespace std;
const int MAXN=5000000;
int x[MAXN];
int main()
{
    int n,k,t;
    cin>>n>>k;
    for(int i=0;i<n;i++)
      cin>>x[i];
    sort(x,x+n);
    cout<<x[k]<<endl;
    return 0;
}

by Sya_Resory @ 2021-11-07 14:43:10

1. 因为这题正解不是快排
2. 请使用 nth_element

by Jorisy @ 2021-11-07 14:43:12

nth_element()了解一下

by 软糖RT @ 2021-11-07 14:43:19

快排被卡可能

by _slb @ 2021-11-07 14:43:33

快拍复杂度 O(n\log n)，本题 n=5\times 10^6，当然过不去，你得用个 O(n) 的算法

by bh1234666 @ 2021-11-07 14:50:04

建议基排

反正我用基排艹过去了

by afowww @ 2021-11-12 23:31:38

不用sort，自己手写快排+快读可以过。 P1177 10万的数据手写快排+快读，单点用时13ms，这个500万的数据，单点759ms过的

by Fetter123 @ 2021-11-14 09:19:16

@Forever_coding 快读的代码能写一下吗，我不太会

by Xeres @ 2022-02-22 02:08:35

1、手写快排可以过，递归的时候只递归一部分就行：

if(k==blank) return;
else if(k<blank){
    qsort(nums,start,blank-1,k);
}else{
    qsort(nums,blank+1,end,k);
}

2、快排key的选取可以用一下随机数

3、另外，用scanf()会快很多,cin被卡是日常了