这个是一个叫做randomized-select的算法，这个算法巧妙地运用了快速排序的特性。同时这个算法的期望时间为O(n).
这是算法导论上的一节内容，为了方便理解，所以就写给出算法的伪代码，并加以解释：
RANDOMIZED-SELECT(A, p, r, i)
1 if(p==r)
2 return A[p];
3 q=RANDOMIZED-PARTITION(A,p,r);
4,k=q-p+1
5 if(i==k)
6 return A[k]
7 if(i<k)
8 return RANDOMIZED-SELECT(A,p,q-1,i);
9 else return RANDMOIZED-SELECT(A,q+1,r,i)
在第三行代码执行之后，将数组A分为两个子数组，分为为A[p,q-1]和A[q+1,r].前一个数组的元素值均小于或者等于A[q],后个数组中的值均大于等于A[q]。第四行是计算A[p,q]中数组元素的个数。第5行是判断A[k]是不是第i小元素，如果是，那就返回。如果不是在第7行到第9行就判断，第i小元素落在哪个子数组中。根据第三行的执行结果，如果i<k。说明落在A[p,q-1]中，若i>k，则说明落在A[q+1,r]中，因为已经知道有k个元素即A[p,q]，小于A[q+1,r]中的第i小元素，故所求的元素必为A[q+1,r]中第i-k小元素。上述代码中SANDOMIZED-PARTITION和快速排序中的一样，所以就不给出了。
#include <stdio.h>
#include<stdlib.h>
int randomized_partition(int *a,int low,int high)
{//找到分界点
int pivot=a[low];
while(low<high)
{
while(low<high&&a[high]>=pivot)
high--;
a[low]=a[high];
while(low<high&&a[low]<=pivot)
low++;
a[high]=a[low];
}
a[low]=pivot;
return low;
}
int randomized_select(int *a,int low,int high,int i)
{
if(low==high)
return a[low];
int pivot=randomized_partition(a,low,high);
int k=pivot-low+1;
if(k==i)
return a[pivot];
else if(i<k )
return randomized_select(a,low,pivot-1,i);
else
return randomized_select(a,pivot+1,high,i-k);
}
int main()
{
int a[]={1,34,5,16,37,28,9,13,26};
int result=randomized_select(a,0,sizeof(a)/sizeof(int)-1,2);
printf("%d\n",result);
return 0;
}