找最轻最重 快排思想 第K大

【金块问题】有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。

#include<iostream>
usingnamespace std;
intn,flag=0,a[100];
intPartition(int a[],int p,int r){
int j=r+1,i=p,x=a[p];
while(true){
while(a[++i]
while(a[--j]>x);
if(i>=j)break;
swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
voidf(int a[],int p,int r){
while(p
intt=Partition(a,p,r);
if(t==0){
if(flag)return;    //此时flag为1，最大值已取得 
else flag++;          
}
else if(t==n-1)
{
if(flag) return;//此时flag为1,最小值已取得。即此时最大最小值已得到     
else flag++;
}
f(a,p,t-1);
f(a,t+1,r);
}
}
intmain(){
while(cin>>n&&n>1){
for(int i=0;i>a[i];
flag=0;       //在算法中做标志，最小最大值未知，先置为0 
f(a,0,n-1);
cout<<a[0]<<''<<a[n-1]<<endl;
}
return0;
}