问题遇到的现象和发生背景
题目是输出数组第k大元素，要求多组输入，第一行是k,第二行是数组，要求时间复杂度为O(n)，用数据分区+递归查找加随机选取基准就可以,我明明用的是归并排序但oj老是时间超限。
问题相关代码，请勿粘贴截图
#include<stdio.h>
#include<stdlib.h>
int main(){
int n;
int a[10000];
char c;
int k;
while(scanf("%d",&k)!=EOF){
while(scanf("%d",&a[0])!=EOF){
int n=0;
while(scanf("%d",&a[++n])){
if(c=getchar()=='\n')
break;
}
int result=quickselect(a,0,n,k);
printf("%d\n",result);
}
}
return 0;
}
void swap(int a[],int i,int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
int random(int p,int q){
return rand()%(q-p+1)+p;
}
int rpart(int a[],int p,int q){
int r=random(p,q);
swap(a,p,r);
int i=part(a,p,q);
return i;
}
int part(int a[],int p,int q){
int x=a[p];
int i=p,j;
for(j=p+1;j<=q;j++){
if(a[j]>=x){
i++;
swap(a,i,j);
}
}
swap(a,p,i);
return i;
}
int quickselect(int a[],int p,int q,int k){
if(p==q){
return a[p];
}
else{
int i=rpart(a,p,q);
int j=i-p+1;
if(k<=j){
return quickselect(a,p,i,k);
}
else{
return quickselect(a,i+1,q,k-j);
}
}
}
运行结果及报错内容
我的解答思路和尝试过的方法
想问问我这个代码需要改进什么地方
