算法导论第九章例题9.2
在O(n)时间内选择第i小的元素。该算法利用了快速排序的思想，首先根据某元素对数组进行划分，然后判断第i个小元素是在前面数组还是后面数组，然后对该数组继续进行划分，直到找到第i小元素。
示例代码如下：
#include<iostream>using namespace std;int RandomdisePartition(int a[] ,int p,int r){int i,j,temp,num;num=a[r];j=p-1;for(i=p;i<r;i++){if(a[i]<num){j++;temp=a[i];a[i]=a[j];a[j]=temp;}}temp=a[r];a[r]=a[j+1];a[j+1]=temp;return j+1;}int RandomizSelect(int a[],int p,int r,int num){if(p==r){return a[p];}int q=RandomdisePartition(a,p,r);int k=q-p+1;if(k==num){return a[q];}else if(num<k){return RandomizSelect(a,p,q-1,num);}else{return RandomizSelect(a,q+1,r,num-k);}}int main(){int a[10]={2,56,48,685,4596,16,48,748,742,1635};int num=RandomizSelect(a,0,9,5);cout<<num<<endl;return 0;}