算法导论第九章习题9.2-3

使用迭代版本的随机选择函数实现选择第i小元素。原理与9.2例题相同，该代码为9.2例题的迭代版实现。具体代码如下：

#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 RandomizSelectInIterater(int a[],int p,int r,int num){if(p==r){return a[p];}while(1){int q=RandomdisePartition(a,p,r);int k=q-p+1;if(k==num){return a[q];}else if(num<k){r=q-1;}else{p=q+1;num=num-k;}}}int main(){int a[10]={2,56,48,685,4596,16,48,748,742,1635};int num=RandomizSelectInIterater(a,0,9,5);cout<<num<<endl;return 0;}