第K选择问题

[c++]代码库

//第k选择问题  第k小问题
#include<iostream>
using namespace std;
int partition(int r[],int first,int end)
{
	int i,j;
	i=first;
	j=end;
	while(i<j)
	{
		while(i<j&&r[i]<=r[j])
			j--;
		if(i<j)
		{
			swap(r[i],r[j]);
			i++;
		}
		while(i<j&&r[i]<=r[j])
			i++;
		if(i<j)
		{
			swap(r[j],r[i]);
			j--;
		}
	}
	return i;
}
int select(int a[],int m,int n,int r)
{
	int pos;
	pos=partition(a,m,n);
	if(pos==r) return r;
	if(r<pos)
		return select(a,m,n-1,r);
	else
		return select(a,m+1,n,r);
}
int main()
{
	int i,n,a[100],k;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>k;
	int pos;
	pos=select(a,1,n,k);
/*	cout<<zhouzhi(a,1,n)<<endl;//显示轴值位置
	kuai(a,1,n);
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;*/
	cout<<a[pos]<<endl;
	return 0;
}

[源代码打包下载]