任意输入n个数，求第k大的数？用C语言，写出完整代码。

Question

如题所述

Answer 1

#include<stdio.h>
int main(){
int a[10000];
int n,temp,i,k,j;
printf("请输入你要输入的数的个数n：\n");
scanf("%d",&n);
for(i=0;i<n;i++){
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(a[j]<a[i]){
temp=a[j];
a[j]=a[i];
a[i]=temp;}
}
}

printf("请输入你要的到第几小/大的数K:\n");
scanf("%d",&k);
printf("第%d大的数为%d\n",k,a[k-1]);
printf("第%d小的数为%d\n",k,a[n-k]);
return 0;
}

Answer 2

#include "iostream"
#include "stdlib.h"
using namespace std;

int random_partion(int *p, int n)
{
int idx=rand()%n;
swap(p[idx], p[n-1]);
int i=-1;    //i????????p[n-1]??????
int j=0;     //j??????
for(j=0; j<n; j++)
{
//???p[n-1]?????????
if(p[j]<p[n-1])
{
swap(p[++i], p[j]);
}
}
swap(p[++i], p[n-1]);
return i;
}

int getMaxK(int *p, int n, int k)
{
int mid;
if(k<=0)
return -1;
if(n<k)
return -1;
mid=random_partion(p, n);   //??????????
if(mid == n-k)      //??mid==n-k,??????,????k???
return p[mid];
else if(mid<n-k)
return getMaxK(p+mid+1, n-mid-1, k);  //??mid<n-k,???k????????,??????k??
else
return getMaxK(p, mid, k-(n-mid));   //??mid>n-k,???k????????,?????????k-(n-mid)???
}

int main(void)
{
int num,a[] = {12012, 3, 945, 965, 66, 232, 65, 7, 8, 898, 56, 878, 170, 13, 5};
num=getMaxK(a, 15, 4);
int i;
for(i=0;i<15;i++)
{
printf("%7d",a[i]);
}
puts("\n");
printf("%d\n",num);
system("pause");
return 0;
}