利用快速排序从大量数据中查寻最大的若干个数据

利用快速排序从大量数据中查找最大的若干个数据

/*
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]区间中的数大于n
				Solution(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();
}