题目是输出数组第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);
}
}
}
想问问我这个代码需要改进什么地方
题目呢？另外快排时间复杂度也是O(nlogn)啊
归并排序：
#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;
}