topk的两种算法C++实现（堆，快速查找）

#include
using namespace std;

int topk(vector<int> arr,int k)//堆方式 
{
	if(k>arr.size()||k<=0)
	{
		return -1;
	}
	priority_queue<int,vector<int>,greater<int> > qp;
	for(int i=0;i<arr.size();i++)
	{
		if(qp.size()<k)
		{
			qp.push(arr[i]);
		}
		else
		{
			if(qp.top()<arr[i])
			{
				qp.pop();
				qp.push(arr[i]);
			}
		}
	}
	return qp.top();
}

int topk2main(vector<int>& arr,int k,int l,int r)
{
	if(l>r)
	{
		return -1;
	}
	int temp = arr[l];
	int i=l;
	int j=r;
	while(i<j)
	{
		while(i<j&&arr[j]>=temp) j--;
		while(i<j&&arr[i]<=temp) i++;
		if(i<j)
		{
			swap(arr[i],arr[j]);
		}
	}
	arr[l]=arr[i];
	arr[i]=temp;
	
	if(r-i+1==k)
	{
		return arr[i];
	}
	else if(r-i<k)
	{
		return topk2main(arr,k+i-r-1,l,i-1);
	}
	else
	{
		return topk2main(arr,k,i+1,r);
	}
}

int topk2(vector<int> arr,int k)//快速选择方式 
{
	if(k>arr.size()||k<=0)
	{
		return -1;
	}
	return topk2main(arr,k,0,arr.size()-1);
}

void test(vector<int> arr)
{
	bool flag = false;
	for(int i=0;i<=1000;i++)
	{
		int a=topk(arr,i);
		int b=topk2(arr,i);
		int c=a==b?1:0;
		cout<<a<<"\t";
		cout<<b<<"\t";
		cout<<c<<endl;
		if(c==0)
		{
			flag=true;
		}
	}
	if(flag)
	{
		cout<<"ERROR!"<<endl;
	}
	else
	{
		cout<<"YES!"<<endl;
	}
	cout<<endl;
}

int main()
{
	srand(time(NULL));
	vector<int> arr;
	for(int i=0;i<1000;i++)
	{
		arr.push_back(rand()%2000);
	}
	test(arr);
}