算法实际上是模仿快速排序算法设计出来的，其基本思想也是对输入数组进行递归划分，与快速排序不同的是，它只对划分出来的子数组之一进行递归处理；
int randompartition(int a[],int l,int r)
{
int i=l-,j=r,v=a[r],tmp;
for(;;)
{
while(a[++i]<v);
while(a[--j]>v)if(j==l)break;
if(i>=j)break;
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
tmp=a[i];a[i]=a[r];a[r]=tmp;
return i;
}
randompartition产生的划分基准是随机的，在这个条件下，可以证明算法randomselect可以在o(n)平均时间内找出n个输入元素的第k小元素。
消除randomselect尾递归的算法如下：
int randomselect(int a[],int l,int r,int k)
{
int i,j;
while(l<r)
{
i=randompartition(a,l,r);
j=i-l+;
if(j==k)
return a[i];
if(j>k)
r=i-;
else
{
l=i+;
k-=j;
}
}
return ((r<i)?a[l]:a[r]);
}
解决算法与数据结构实验题10.1神谕者：
#include<stdio.h>
int a[];
int randompartition(int a[],int l,int r)
{
int i=l-,j=r,v=a[r],tmp;
for(;;)
{
while(a[++i]<v);
while(a[--j]>v)if(j==l)break;
if(i>=j)break;
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
tmp=a[i];a[i]=a[r];a[r]=tmp;
return i;
}
int randomselect(int a[],int l,int r,int k)
{
int i,j;
while(l<r)
{
i=randompartition(a,l,r);
j=i-l+;
if(j==k)
return a[i];
if(j>k)
r=i-;
else
{
l=i+;
k-=j;
}
}
return ((r<i)?a[l]:a[r]);
}
int main()
{
int n,m,i,len,x,y;
scanf("%d %d",&n,&m);
for(i=;i<n;i++)
{
scanf("%d",&a[i]);
}
len=n;
for(i=;i<m;i++)
{
scanf("%d %d",&x,&y);
if(x==)
a[len++]=y;
else
printf("%d\n",randomselect(a,,len-,y));
}
return ;
}