sort.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

//  排序算法数据结构 Sort.h     // 
//    // 
////////////////////////// 

#include <iomanip.h>
#include<iostream.h>
#include "stack.h" 
template<class Type> 
class Sort				//定义排序类
{ 
public: 
	Sort():sort(NULL){} 
	void Creat();    //创建排序数组 
	void Bubble(); //冒泡排序  
	void Insert(); //插入排序 
//快速排序 
	void Quick();  
	void QSort(int,int); 
	int Partition(int low,int high); 
	int Partition(Type a[],int p,int r);//重载分组
	void QuickSort(Type a[],int p,int r);//重载快速排序
	void QuickSort(int s,int t);
//归并排序 
	void Merge(Type SR[],Type TR[],int i,int m,int n); 
	void Msort(Type SR[],Type TR1[],int s,int t); 
	void MergeSort(); 
//选择排序 
	void Select(); 
	void Print();   //打印排序后的结果 
	int GetLen(){return leng;}
protected: 
	Type *sort; 
	int leng; 
}; 

template<class Type> 
void Sort<Type>::Creat() //定义一个长为length的数组
{ 
	cout<<"输入你需要排序的数据个数: "; 
	cin>>leng; 
	while(leng<=0) 
	{ 
		cout<<"输入数据有误"; 
		cin>>leng; 
	} 
	sort=new Type[leng]; 
	cout<<"请输入各数据项："; 
	for(int i=0;i<leng;i++) 
	cin>>sort[i]; 
}  

template<class Type> //插入排序
void Sort<Type>::Insert() 
{ 
	Creat(); 
	Type temp; 
	for(int i=1;i<leng;i++) 
	{ 
		if(sort[i]<sort[i-1]) 
		{ 
			temp=sort[i]; 
			for(int j=i-1;temp<sort[j]&&j>=0;j--) 
			{ 
				sort[j+1]=sort[j]; 
			} 
			sort[j+1]=temp; 
		} 
	} 
	Print(); 
} 

template<class Type> 
void Sort<Type>::Bubble() //冒泡排序
{ 
	Creat(); 
	Type temp; 
	for(int i=leng-1;i>=0;i--) 
	{ 
		for(int j=0;j<leng-1;j++) 
		{ 
			if(sort[j]>sort[j+1]) 
			{ 
				temp=sort[j]; 
				sort[j]=sort[j+1]; 
				sort[j+1]=temp; 
			} 
		} 
	} 
	Print(); 
} 

template<class Type> 
void Sort<Type>::Quick() //快速排序
{ 
	Creat(); 
	QSort(0,leng-1); 
	Print(); 
} 

template<class Type> 
void Sort<Type>::QSort(int s,int t) //快速排序
{ 
	if(s<t) 
	{ 
		int pivotloc=Partition(s,t); 
		QSort(s,pivotloc-1); //对pivotloc左边的排序
		QSort(pivotloc+1,t); //对pivotloc右边的排序
	} 
} 

template <class Type>
int Sort<Type>::Partition(Type a[],int p,int r)
{
	int i=p;
	int j=r+1;
	Type x=a[p],temp;
	while(true)//将大于X的换到左边，小于X的换到右边
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j)break;
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}

template <class Type>//
int	Sort<Type>::Partition(int low,int high)
{
	Type temp=sort[low];
	while(low<high)
	{
		while(low<high&&sort[high]>temp)
			high--;
		sort[low]=sort[high];
		while(low<high&&sort[low]<temp)
			low++;
		sort[high]=sort[low];
	}
	sort[low]=temp;	
	return low;			//或返回high
}

template <class Type>
void Sort<Type>::QuickSort(Type a[],int p,int r)
{
	if(p<r)
	{
		int q=Partition(a,p,r);
		QuickSort(a,p,q-1);//对在边的排序
		QuickSort(a,q+1,r);//对右边的排序
	}
}
template<class Type>
void Sort<Type>::QuickSort(int s,int t)
{
	int i=s,j=t+1;//
	Type x=sort[s];
	do
	{
		do i++;while(sort[i]<x);
		do j--;while(sort[j]>x);
		if(i<j)
		{
			Type temp=sort[i];
			sort[i]=sort[j];
			sort[j]=temp;
		}
	
	}while(i<j);
	sort[s]=sort[j];
	sort[j]=x;
	if(s<j-1)QuickSort(sort,s,j-1);
	if(j+1>1)QuickSort(sort,j+1,t);
}



template<class Type> 
void Sort<Type>::MergeSort() //归并排序
{ 
	Creat(); 
	Msort(sort,sort,0,leng-1); 
	Print(); 
} 


template<class Type> 
void Sort<Type>::Msort(Type SR[],Type TR1[],int s,int t) //归并
{ 
	int m; 
	Type *TR2=new Type[t-s]; 
	if(s==t) TR1[s]=SR[s]; 
	else 
	{ 
		m=(t+s)/2; 
		Msort(SR,TR2,s,m); 
		Msort(SR,TR2,m+1,t); 
		Merge(TR2,TR1,s,m,t); 
	} 
} 

template<class Type> 
void Sort<Type>::Merge(Type SR[],Type TR[],int i,int m,int n) 
{ 
	for(int j=m+1,k=i;i<=m&&j<=n;k++) 
	{ 
		if(SR[i]<=SR[j]) 
			TR[k]=SR[i++]; 
		else 
			TR[k]=SR[j++]; 
	} 
	while(i<=m) 
		TR[k++]=SR[i++]; 
	while(j<=n) 
		TR[k++]=SR[j++]; 
} 

template<class Type> 
void Sort<Type>::Select() //选择排序
{ 
	Creat(); 
	Type temp; 
	int t; 
	for(int i=0;i<leng;i++) 
	{ 
		t=i; 
		for(int j=i+1;j<leng;j++) 
		{ 
			if(sort[t]>sort[j]) 
			t=j; 
		} 
		if(t!=i) 
		{ 
			temp=sort[t]; 
			sort[t]=sort[i]; 
			sort[i]=temp; 
		} 
	} 
	Print(); 
} 

template<class Type> 
void Sort<Type>::Print() //输出数字
{ 
	cout<<"排序结果为: "; 
	for(int i=0;i<leng;i++) 
	cout<<sort[i]<<" "; 
	cout<<endl; 
} 

////////////////////快速排序的非递归实现方法///////////////////////////
void quicksort(int x[],int n)
{
	int i,j;
	struct bndtype
	{
		int lb;
		int ub;
	}newbnds;//stack is used by the pop,push and empty funtions
	struct
	{
		int top;
		struct bndtype bounds[MAXSTACK];
	}stack;
	stack.top=-1;
	newbnds.lb=0;
	newbnds.ub=n-1;
	push(&stack,&newbnds);//repeat as long as there are any unsorted subarrays on the stack
	while(!empty(&stack))
	{
		popsub(&stack,&newbnds);
		while(newbnds.ub>newbnds.lb)
		{
			partition(x,newbnds.lb,newbnds.ub,&j);
			if(j-newbnds.lb>newbnds.ub-j)
			{
				i=newbnds.ub;
				newbnds.ub=j-1;
				push(&stack,&newbnds);
				newbnds.lb=j+1;
				newbnds.ub=i;
			}
			else
			{
				i=newbnds.lb
				newbnds.lb=j+1;
				push(&stack,&newbnds);
				newbnds.lb=i;
				newbnds.ub=j-1;
			}
		}	
	}
}