lineartime.h

这是线性时间选择的一个代码

template<class T>
inline void ExChange(T &a,T &b)
{
	T temp;
	temp = a;
	a = b;
	b = temp;
}
template<class T>
void InsertChange(T a[],int i,int j)
{
	//从第i个插到第j个
	T temp;
	int k;
	if(i<j)
	{
		temp = a[i];
		for(k=i+1;k<=j;k++)
		{
			a[k-1]=a[k];
		}
		a[j] = temp;
	}
	else if(i>j)
	{
		temp = a[i];
		for(k=i-1;k>=j;k--)
		{
			a[k+1] = a[k];
		}
		a[j] = temp;
	}
	///////////////////////////
/*	解除注释看步骤
	for(int l=0;l<=9;l++)
	{
		cout<<a[l]<<" ";
	}
	cout<<endl;*/
	/////////////////////////////
}



template<class T>
T LTime(T a[],int i,int p,int q)
{
	//普通线性时间选择
	int j;
	int k = i;
	for(j=p;j<=q;j++)
	{
		if(j<i && a[j]>a[i])
		{
			InsertChange<T>(a,j,i);
			i--;
			j--;
		}
		else if(j>=i && a[j]<a[i])
		{
			InsertChange<T>(a,j,i);
			i++;
			j--;
		}
	}

	if(i == k)
		return a[k];
	else if(i>k)
		return LTime(a,k,p,i-1);
	else
		return LTime(a,k,i+1,q);
}

template<class T>
int LTimeReturnInt(T a[],int i,int p,int q)
{
	//普通线性时间选择
	int j;
	int k = i;
	for(j=p;j<=q;j++)
	{
		if(j<i && a[j]>a[i])
		{
			InsertChange<T>(a,j,i);
			i--;
			j--;
		}
		else if(j>=i && a[j]<a[i])
		{
			InsertChange<T>(a,j,i);
			i++;
			j--;
		}
	}

	if(i == k)
		return k;
	else if(i>k)
		return LTime(a,k,p,i-1);
	else
		return LTime(a,k,i+1,q);
}
////////////////////////////////////////////////////
template<class T>
void SortPopo(T a[],int p,int r)
{	
	//改进的冒泡排序法
	bool flag;
	int i,j;
	for(i=p;i<r-1;i++)
	{
		flag = true;
		for(j=i;j<r;j++)
		{
			if(a[i]>a[j])
			{
				ExChange<T>(a[i],a[j]);
				flag = false;
			}		
		}
		if(flag)break;
	}
}

template<class T>
int Partition(T a[],int p,int r,T x)
{
	int i = p;
	int j = r+1;
	x = a[p];
	while(true)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j)break;
		ExChange(a[i],a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j;
}

template<class T>
T Select(T a[],int p,int r,int k)
{
	if(r-p<75)
	{
		SortPopo(a,p,r);
		return a[p+k-1];
	}
	for(int i=0;i<=(r-p-4)/5;i++)
	{
		ExChange(a[p+i],a[LTimeReturnInt(a,2,p+5*i,p+5*i+4)]);
	}
	T x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);
	 i = Partition(a,p,r,x);
	int j = i - p + 1;
	if(k <= j) return Select(a,p,i,k);
	else return Select(a,i+1,r,k-j);
}