一种查找k个最小元素的方法

/*This is a free Program, You can modify or redistribute it under the terms of GNU*Description:一种查找k个最小元素的方法*Language: C++*Development Environment: VC6.0*Author: Wangzhicheng*E-mail: 2363702560@qq.com*Date: 2012/11/25*/#include <iostream>#include <vector>#include <set>#include <ctime>#include <algorithm>using namespace std;/**此种方法原理比较简单,即利用一个空间大小是k的multiset*将原始数据的前k个依次插入multiset,然后从元素数据的第k+1个元素开始*逐渐与multiset的第一个元素比较,(注意,multiset是用红黑树实现的,可以容纳*多个相同的元素,当比较器是greater时,multiset第一个元素是最大的元素),如果比*第一元素小,则删除mutiset第一个元素,将此元素插入*/template<class Type>class FindKMinElemFromVector {public:void Method_Of_SortedK(vector<Type>&v,int k) {multiset<Type,greater<Type> >assistant;vector<Type>::iterator it;for(it=v.begin();it!=v.begin()+k;it++) {assistant.insert(*it);}for(;it!=v.end();it++) {multiset<Type,greater<Type> >::iterator Max_it=assistant.begin();if(*it<*Max_it) {assistant.erase(Max_it); //此时不能写成*Max_it,这样会删除多个相同的元素assistant.insert(*it);}}multiset<Type,greater<Type> >::iterator it1;cout<<k<<"个最小数据是:"<<endl;for(it1=assistant.begin();it1!=assistant.end();it1++) {cout<<*it1<<" ";}cout<<endl;}};void main() {FindKMinElemFromVector<int>ff;srand(unsigned(time(0)));int N=20;int i=0;vector<int>v;int x;for(i=0;i<N;i++) {v.push_back(rand()%N);}cout<<"原始数据是:"<<endl;copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));cout<<endl;ff.Method_Of_SortedK(v,3);}

测试：