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

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

 1 int randomselect(int a[],int l,int r,int k)
 2 {
 3     int i,j;
 4     while(l<r)
 5     {
 6         i=randompartition(a,l,r);
 7         j=i-l+1;
 8         if(j==k)
 9             return a[i];
10         if(j>k)
11             r=i-1;
12         else
13         {
14             l=i+1;
15             k-=j;
16         }
17     }
18     return ((r<i)?a[l]:a[r]);
19 }

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

 1  
 2             #include<stdio.h>
 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);
10         while(a[--j]>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<r)
23     {
24         i=randompartition(a,l,r);
25         j=i-l+1;
26         if(j==k)
27             return a[i];
28         if(j>k)
29             r=i-1;
30         else
31         {
32             l=i+1;
33             k-=j;
34         }
35     }
36     return ((r<i)?a[l]:a[r]);
37 }
38 int main()
39 {
40     int n,m,i,len,x,y;
41     scanf("%d %d",&n,&m);
42     for(i=0;i<n;i++)
43     {
44         scanf("%d",&a[i]);
45     }
46     len=n;
47     for(i=0;i<m;i++)
48     {
49         scanf("%d %d",&x,&y);
50         if(x==0)
51             a[len++]=y;
52         else
53             printf("%d\n",randomselect(a,0,len-1,y));
54     }
55     return 0;
56 
57 }
58 
59
View Code