给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素
#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);
else
return 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;
}