求前k个最小的数---类似快排思想的O（n）

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int Partition(vector<int>&data,int headId,int tailId)
{
	int posSlow = headId-1,posFast=headId;
	for(;posFast<tailId;++posFast)
	{
		if(data[posFast]<data[tailId])
		{
			++posSlow;
			swap(data[posSlow],data[posFast]);
		}
	}
	++posSlow;
	swap(data[posSlow],data[tailId]);
	return posSlow;
}
void FindKLeast(vector<int>&data,int headId,int tailId,int k)
{
	if(headId<tailId)
	{
		int midId=Partition(data,headId,tailId);
		if(midId>k)
		{
			FindKLeast(data,headId,midId-1,k);
		}
		else
		{
			if(midId<k)
			{
				FindKLeast(data,midId+1,tailId,k);

			}
		}
	
	}
}

void FindKLeastNumbers(vector<int>&data,unsigned int k)
{
	int len = data.size();
	if(k>len)
	{
		throw new std::exception("Invalid argument!");
	}
	FindKLeast(data,0,len-1,k);
}

int main()
{
	int a[]={12,42,10,31,6,15};
	int k=3;
	vector<int>::iterator iter;
	vector<int> ivector(a,a+6);
	FindKLeastNumbers(ivector,k);
	cout<<"前k个最小的数为："<<endl;
	for(iter = ivector.begin();iter<=ivector.begin()+k-1;iter++)
		cout<<*iter<<"  ";
	cout<<endl;
}

求前k个最小的数---类似快排思想的O（n）,布布扣,bubuko.com

求前k个最小的数---类似快排思想的O（n）

原文：http://blog.csdn.net/woailvmengmeng/article/details/23421963