030300307integer.cpp

这是一个关于整数字典的源程序

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

template<class T>
inline void Swap(T&a,T&b)
{
	//交换a与b的值
	T temp=a;
	a=b;
	b=temp;
}

template<class T>
int Partition(T a[],int p,int r)
{
	int i=p,
		j=r+1;
	T x=a[p];
    //将<=x的元素交换到左边区域
    //将>=x的元素交换到右边区域
	while(true)
	{
		while(a[++i]<x&&i<r);
		while(a[--j]>x);
		if(i>=j) break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
template<class T>
int RandomizedPartition(T a[],int p,int r)
{
	int i=p+rand()%(r-p+1);
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}
template<class T>
void RandomizedQuickSort(T a[],int p,int r)
{
	if(p<r)
	{
		int q=RandomizePartition(a,p,r);//对左半段排序
		RandomizedQuickSort(a,p,q-1);//对右半段排序
	}
}
template<class T>
T RandomizedSelect(T a[],int p,int r,int k)
{
	if(p==r) return a[p];
	int i=RandomizedPartition(a,p,r),
		j=i-p+1;
	if(k==j) return a[i];
	else if(k<j) return RandomizedSelect(a,p,i-1,k);
	else return RandomizedSelect(a,i+1,r,k-j);
}

int main()
{
	int m,n,k=1;
	in>>m>>n;
	int *a=new int[m];
	int *b=new int[n];
	for(int i=0;i<m;i++)
		in>>a[i];
	for(i=0;i<n;i++)
	{
		in>>b[i];
		int j=RandomizedSelect(a,0,b[i]-1,k++);
		out<<j<<' ';
	}
	out<<endl;
	/*for(int i=1;i<=1000;i++)  out<<i<<' ';*/ 
	return 1;
}