利用快速排序从大量数据中查找最大的若干个数据
/*This is a free Program, You can modify or redistribute it under the terms of GNU*Description:在大量数据中查找最大的若干个数据*Language: C++*Development Environment: VC6.0*Author: Wangzhicheng*E-mail: 2363702560@qq.com*Date: 2012/10/31*//**利用快速排序的方法进行查找,首先将整个待查找的数据放入STL中的向量中,然后依据快速排序的方法递归查找*/#include <iostream>#include <vector>#include <Iterator>#include <algorithm>#include <ctime>using namespace std;const int N=100; //有100个数据template<class Iterator,class Type>class SelectMaxN {private:int n; //选择多少个最大的数据vector<Type>v; //将这些n个最大的数据保存在此向量中Iterator Divide(Iterator start,Iterator finish) {Type temp=*start;while(start<finish) {while(*finish>temp && finish>start) finish--;if(finish>start) *start++=*finish;while(*start<temp && finish>start) start++;if(finish>start) *finish--=*start;}*start=temp;return start;}void Solution(Iterator start,Iterator finish) {Iterator mid=Divide(start,finish-1);if(finish-mid==n) { //此时最大的n个元素已经生成find(start,finish);return;}else if(finish-mid>n) { //此时[mid,finish-1]区间中的数大于nSolution(mid+1,finish);}else { //此时[mid,finish-1]区间中已经出现了最大的如干个数int i=0; //用来计算从[mid,finish-1]区间中有多少个数Iterator it=finish-1;while(it>=mid) {v.push_back(*it--);i++;}n-=i; //需要在[start,mid-1]区间中查找n-i个最大的数 Solution(start,mid-1);}}void find(Iterator start,Iterator finish) {int i;Iterator it=finish-1;for(i=0;i<n && it>=start;i++) {v.push_back(*it--);}}public:SelectMaxN(Iterator start,Iterator finish,int n) {if(n>finish-start) this->n=finish-start; //n已经超过所有数据个数this->n=n;Solution(start,finish);}void show() {vector<Type>::iterator it;for(it=v.begin();it!=v.end();it++) {cout<<*it<<" ";}cout<<endl;}};void main() {srand(unsigned(time(0)));vector<int>a;int i;for(i=0;i<N;i++) { //随机生成N个整数a.push_back(rand()%N);cout<<a[i]<<" ";}cout<<endl;SelectMaxN<vector<int>::iterator,int>aa(a.begin(),a.end(),8);aa.show();}