OJ时间超限问题，代码能改进什么地方

Question

问题遇到的现象和发生背景

题目是输出数组第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);
}
}

}

运行结果及报错内容

我的解答思路和尝试过的方法

想问问我这个代码需要改进什么地方

我想要达到的结果

Answer 1

题目呢？另外快排时间复杂度也是O(nlogn)啊

Answer 2

归并排序：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

void Merge(int R[], int low, int m, int high)
{
    //将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]  
    int i = low, j = m + 1, p = 0;                //置初始值  
    int* R1;                        //R1是局部向量  
    R1 = (int*)malloc((high - low + 1) * sizeof(int));
    if (!R1)
    {
        return;                         //申请空间失败  
    }

    while (i <= m && j <= high)                //两子文件非空时取其小者输出到R1[p]上  
    {
        R1[p++] = (R[i] <= R[j]) ? R[i++] : R[j++];
    }

    while (i <= m)                         //若第1个子文件非空，则复制剩余记录到R1中  
    {
        R1[p++] = R[i++];
    }
    while (j <= high)                      //若第2个子文件非空，则复制剩余记录到R1中  
    {
        R1[p++] = R[j++];
    }

    for (p = 0, i = low; i <= high; p++, i++)
    {
        R[i] = R1[p];                     //归并完成后将结果复制回R[low..high]  
    }
}

void MergeSort(int R[], int low, int high)
{
    //用分治法对R[low..high]进行二路归并排序  
    int mid;
    if (low < high)
    {   //区间长度大于1   
        mid = (low + high) / 2;               //分解  
        MergeSort(R, low, mid);           //递归地对R[low..mid]排序  
        MergeSort(R, mid + 1, high);        //递归地对R[mid+1..high]排序  
        Merge(R, low, mid, high);          //组合，将两个有序区归并为一个有序区  
    }
}

int main()
{
    int n;
    int a[10000];
    char c;
    int k;
    while (scanf("%d", &k) != EOF)
    {
        n = 0;
        while (scanf("%d", &a[n]))
        {
            n++;
            c = getchar();
            if (c == '\n')
                break;
        }

        MergeSort(a, 0, n - 1);
        printf("%d\n", a[n - k]);
    }
    return 0;
}

Answer 3

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632