线性时间选择

#include<iostream>
#include<cstdlib>
#include<time.h>
using namespace std;
int a[100];
int Random(int left,int right)
{srand(time(NULL));return rand()%(right-left+1)+left;
}
int PartSort(int left,int right)
{int key=Random(left,right);swap(a[left],a[key]);while(left<right){while(left<right&&a[right]>=a[key])right--;while(left<right&&a[left]<=a[key])left++;if(left<right)swap(a[left],a[right]);}swap(a[key],a[left]);return left;
}
int RandomizedSelect(int left,int right,int k)
{if(left==right)return a[left];int key=PartSort(left,right);int j=key-left+1;if(j==k)return a[key];if(k<j)return RandomizedSelect(left,key,k);elsereturn RandomizedSelect(key+1,right,k-j);}
int main()
{int n,k;cin>>n>>k;for(int i=0;i<n;i++)cin>>a[i];cout<<RandomizedSelect(0,n-1,k)<<endl;return 0;
}