算法实际上是模仿快速排序算法设计出来的，其基本思想也是对输入数组进行递归划分，与快速排序不同的是，它只对划分出来的子数组之一进行递归处理；

int randompartition(int a[],int l,int r){    int i=l-1,j=r,v=a[r],tmp;    for(;;)    {        while(a[++i]
     
      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尾递归的算法如下：

1 int randomselect(int a[],int l,int r,int k) 2 { 3     int i,j; 4     while(l
     
      k)11             r=i-1;12         else13         {14             l=i+1;15             k-=j;16         }17     }18     return ((r
     

解决算法与数据结构实验题10.1神谕者：

1   2             #include
      
        3 int a[50005]; 4 int randompartition(int a[],int l,int r) 5 { 6     int i=l-1,j=r,v=a[r],tmp; 7     for(;;) 8     { 9         while(a[++i]
       
        v)if(j==l)break;11         if(i>=j)break;12         tmp=a[i];13         a[i]=a[j];14         a[j]=tmp;15     }16     tmp=a[i];a[i]=a[r];a[r]=tmp;17     return i;18 }19 int randomselect(int a[],int l,int r,int k)20 {21     int i,j;22     while(l
        
         k)29             r=i-1;30         else31         {32             l=i+1;33             k-=j;34         }35     }36     return ((r