问题标题: 酷町堂：4210 k小元素（数据量加大）

题目描述 Description

对于给定的n个整数，请聪明的你输出其中第m小的数。

输入描述 Input Description

输入两行；
第一行输入整数n和k，n和k之间用空格隔开（0<k<=n<=1500000)。
第二行输入n个整数，数与数之间用空格隔开。

输出描述 Output Description

输出为一行，为n个整数中第k小的数。

 

初看数据，感觉快排不会TLE

结果提交TLE70

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
long long a[1500005];
int n,k;
void ksort(long long a[],int l,int r){
    int i=l,j=r,mid=a[(l+r)/2];
    while(i<=j){
        while(a[i]<mid) i++;
        while(mid<a[j]) j--;
        if(i<=j){
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if(l<j) ksort(a,l,j);
    if(i<r) ksort(a,i,r);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ksort(a,1,n);
    cout<<a[k];
    return 0;
}

求正解