kuai.h

改进的快速排序程序

template <typename My> bool Kuai1(My*p,int num)//简单快速排序,升序,O(N log2 N)
{
	if(num<=1)return true;///递归终止条件
	int i;
	My *temp;
	temp=new My[num];
	if(!temp)
		return false;
	int tsmall=0,big=num-1;//升序
	for(i=1;i<num;i++)
	{
		My &a=p[i];
		if(a>p[0])//大的
		{
			temp[big]=a;
			big--;
		}
		else
		{
			temp[tsmall]=a;
			tsmall++;
		}
	}
	temp[big]=p[0];
	for(i=0;i<num;i++)
	{
		p[i]=temp[i];
	}
	delete[]temp;
	if(Kuai1(p,big) && Kuai1(p+big+1,num-big-1))
	{
		return true;
	}
	return false;
}

template <typename My> bool Kuai2(My*p,int num)//稍作改进
{
//	cout<<"进入函数  "<<num<<endl;
	int i;
	int n_small=1,n_big=num-1;//升序
	My m_key=p[0];
	bool xiaokong=true;//小头有空
	My *p_free=p;

	if(num<=1)return true;///递归终止条件
	for(i=0;i<num-1;i++)
	{
/*
		for(int i=0;i<num;i++)
		{
			cout<<' '<<p[i];
		}
		cout<<endl<<endl;
*/
		if(xiaokong)//小头有空//从大头取元素
		{
			if(p[n_big]<m_key)//小的
			{
				*p_free=p[n_big];
				p_free=p+n_big;
				n_big--;
				xiaokong=false;
			}
			else
			{
				n_big--;
			}
		}
		else//大头有空
		{
			if(p[n_small]<m_key)//小的
			{
				n_small++;
			}
			else
			{
				*p_free=p[n_small];
				p_free=p+n_small;
				n_small++;
				xiaokong=true;
			}
		}
	}
	*p_free=m_key;
/*
	for(i=0;i<num;i++)
	{
		cout<<' '<<p[i];
	}
	cout<<endl<<endl;
	cout<<"此时 n_big="<<n_big<<" n_small="<<n_small<<endl;//<<" ="<<<<" ="<<<<" ="<<<<" ="<<<<" ="<<;
*/
	int num1=p_free-p;
	int num2=num-num1-1;
//	cout<<"进入递归：p:"<<p<<' '<<num1<<"个 "<<num2<<"个。"<<endl;
	if(Kuai2(p,num1) && Kuai2(p+num1+1,num2))
	{
//		cout<<"递归返回。"<<endl;
		return true;
	}
	return false;
}


template <typename My> bool Kuai3(My*p,int num)//又稍作改进（可是速度变慢了）
{
	if(num<=1)return true;///递归终止条件
	int i;
	int n_small=1,n_big=num-1;//升序
	My m_key=p[0];
	bool xiaokong=true;//小头有空
	My *p_free=p;
	My *a;
	for(i=0;i<num-1;i++)
	{
		if(xiaokong)//小头有空
		{
			a=&(p[n_big]);//从大头取元素
		}
		else//大头有空
		{
			a=&(p[n_small]);
		}
		bool a_small=*a<m_key;
		if(a_small && xiaokong || !a_small && !xiaokong)//
		{
			*p_free=*a;
			if(xiaokong)
			{
				p_free=p+n_big;
				n_big--;
			}
			else
			{
				p_free=p+n_small;
				n_small++;
			}
			xiaokong=!xiaokong;
		}
		else
		{
			if(xiaokong)
			{
				n_big--;
			}
			else
			{
				n_small++;
			}
		}
	}
	*p_free=m_key;
	if(Kuai3(p,n_big) && Kuai3(p+n_small,num-n_big-1))
	{
		return true;
	}
	return false;
}//



	

template <typename T> void MaoPao(T* a,int n)//冒泡排序，用于与之对比
{
	bool noswap;//o(n2/2)
	int i,j;
	T temp;
	for (i=0;i<n-1;i++){             //最多做n-1趟
		noswap=true;	              //未交换标志为真
		for(j=n-1;j>i;j--){          //从下往上冒泡
			if(a[j]<a[j-1]){
				temp=a[j];
				a[j]=a[j-1];
				a[j-1]=temp;
				noswap=false;
			}			
		}
		if(noswap) break;	         //本趟无，则终止算法。
	}
}


template <typename My> void Kuai4(My*p,int num)
{
	int i;
	int n_small=1,n_big=num-1;//升序
	My m_key=p[0];
	bool xiaokong=true;//小头有空
	My *p_free=p;

//	if(num<=1)return true;///递归终止条件
	for(i=0;i<num-1;i++)
	{
		if(xiaokong)//小头有空//从大头取元素
		{
			if(p[n_big]<m_key)//小的
			{
				*p_free=p[n_big];
				p_free=p+n_big;
				n_big--;
				xiaokong=false;
			}
			else
			{
				n_big--;
			}
		}
		else//大头有空
		{
			if(p[n_small]<m_key)//小的
			{
				n_small++;
			}
			else
			{
				*p_free=p[n_small];
				p_free=p+n_small;
				n_small++;
				xiaokong=true;
			}
		}
	}
	*p_free=m_key;
	int num1=p_free-p;
	int num2=num-num1-1;
	if(num1>1)
		Kuai4(p,num1);
	if(num2>1)
		Kuai4(p+num1+1,num2);
	return;
}

template <typename My> void Kuai5(My*p,int num)
{
	int i;
	int n_small=1,n_big=num-1;//升序
	My m_key=p[0];
	int n_free=0;
	bool xiaokong=true;//小头有空
	
	for(i=0;i<num-1;i++)
	{
		if(xiaokong)//小头有空//从大头取元素
		{
			if(p[n_big]<m_key)//小的
			{
				p[n_free]=p[n_big];
				n_free=n_big;
				xiaokong=false;
			}
			n_big--;
		}
		else//大头有空
		{
			if(p[n_small]>m_key)//大的
			{
				p[n_free]=p[n_small];
				n_free=n_small;
				xiaokong=true;
			}
			n_small++;
		}
	}
	p[n_free]=m_key;
	int num1=n_free;
	int num2=num-num1-1;
	if(num1>1)
		Kuai5(p,num1);
	if(num2>1)
		Kuai5(p+num1+1,num2);
	return;
}