#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<time.h>
using namespace std;
int random(int p,int r)
{return (rand()%(r-p+1)+p);}
int partion(float a[],int p,int r)
{int x = a[r];  int i=p-1;  for(int j = p;j<r;++j){  if(a[j]<=x){  ++i;  swap(a[i],a[j]);  }  }  swap(a[i+1],a[r]);  return i+1;   
}
int part(float a[],int p,int r)
{int i=random(p,r);swap(a[i],a[p]);return partion(a,p,r);
}//该算法的主体框架为快速排序的框架，但与快速排序不同的是，快速排序是通过递归框架
//对数组进行排序，但此算法通过递归框架只对数组中的第k元进行筛选，所以递归的出口不同
//快速排序中的递归出口为if(high>low)，但该函数的递归出口为if(k-1==i-p)
//与快速排序相同的是都存在一个划分过程
//如果单是求第k元的话，该函数的参数可以简化，即p=0，这样j==i
float select(float a[],int p,int r,int k)
{//在数组a中从下标p到r中求第k小的元素if(p==r){return a[p];}int i=part(a,p,r);//对数组a随机划分int j=i-p;//+1;//此处之所以要i-p因为该函数从数组p下标开始，而不一定从0开始if(k-1==j)//因为数组下标从0开始，所以第k小元素下标为k-1return a[i];//递归出口，返回该元素else if(k-1<j)return select(a,p,i-1,k);elsereturn select(a,i+1,r,k-j-1);}
void bubble(float a[], int n)
{int i,flag=1;for(i=1;i<=n-1&&flag;i++){flag=0;for(int j=0;j<n-i;j++){if(a[j+1]<a[j]){int temp=a[j];a[j]=a[j+1];a[j+1]=temp;flag=1;}}}
} 
int main()
{int n,t,i,j=0;cout<<"请输入元素的个数n"<<endl;cin>>n;
//	float *p=(float *)malloc(n*sizeof(float));float *p=new float[n];cout<<"请输入每个元素的值"<<endl;for(i=0;i<n;i++){cin>>p[i];}cout<<"请输入要寻找第k元的k值"<<endl;int k;cin>>k;cout<<select(p,0,n-1,k)<<endl;return 1;
}