exp10_2.cpp

高等教育出版社出版的C++程序设计同步实验范例 希望对用这本教材得同学有点帮助

/*交换排序中的快速排序（quick sort），也称分区排序，因有最好的平均性能而应用最广。
[算法]
基本思想是：在当前的无序区a[l]到a[h]中任取一个元素作为比较的"基准"（记为temp）。
以此为界，把当前无序区划分为左右两个较小的无序子区：a[l]到a[i-1]和a[i+1]到a[h]。
且左边的无序子区中元素的关键字均小于或等于"基准"temp的关键字；右边的无序子区中元
素的关键字均大于或等于"基准"temp的关键字，这样基准temp则位于最终排序的位置上，即：
a[l]到a[i-1].key<=temp.key<=a[i+1]到a[h].key（l<=i<=h）。下一步可对左右子区，
分别再进行同样的分区过程，直到所有无序子区中的元素均已排好为止。
*/
#include<iostream.h>

template <typename T>struct Node{
	T  key;
	// 其他域省略
};//再次指出分号不可少
template <typename T>class Orderedlist{
	int maxsize;
	int last;
	Node<T> slist[100];
public:
	Orderedlist(){last=-1;maxsize=100;}
	int Length() const{return last+1;}//计算表长度
	int  Partition (const int low,const int high);
	void QuickSort(const int left,const int right);
	bool Insert(Node<T> & elem,int i);
	void print();
	// 无关成员函数省略
};//再次指出分号不可少
template <typename T> bool Orderedlist<T>::Insert(Node<T> & elem ,int i){
	if (i<0||i>last+1||last==maxsize-1) return false;
	else{
		for (int j=last;j>i;j--) slist[j]=slist[j-1];
		slist[i]=elem;
		last++;
		return true;
	}
}
template <typename T> void Orderedlist<T>::print(){
	int i;
	for(i=0;i<=last;i++){
		cout<<slist[i].key<<'\t';
		if(i%8==7) cout<<endl;
	}
	cout<<endl;
}
template <typename T> void Orderedlist<T>::QuickSort(const int left,const int right){
	if(left<right){		//递归算法，对象序列长度大于1，则递归
		int pivotpos=Partition(left,right);//进行分区，一趟排序
		QuickSort(left,pivotpos-1);	//处理左侧子序列
		QuickSort(pivotpos+1,right);//处理右侧子序列
	}
}
template <typename T> int Orderedlist<T>::Partition (const int low,const int high){
	int i=low,j=high;
	Node<T> pivot=slist[low];	//选基准对象
	do{
		while((slist[j].key>=pivot.key)&&(i<j))	j--;//注意从右向左扫描
		if(i<j) slist[i++]=slist[j];//注意slist[j]并没有装slist[i++]内容，见图1.10为空框
		while((slist[i].key<=pivot.key)&&( i<j)) i++;	//从左向右扫描
		if(i<j) slist[j--]=slist[i];//注意上一个if的后++和本次的后--，交换后移一元素
	}while(i!=j);
	slist[i]=pivot;	//最后把空框填入，多设一个pivot，中间每步交换步骤省2/3
	return i;
}

void main(){
	const int h=19;
	int i,k=47;
	Orderedlist<int> ordlist;
	int a[h]={53,7,67,5,41,3,61,59,13,47,23,19,37,29,31,2,17,43,11};
	Node<int> n[h];
	for(i=0;i<h;i++)  n[i].key=a[i];
	for(i=0;i<h;i++)  ordlist.Insert(n[i],i); //建立顺序表
	cout<<"未排序表："<<endl;
	ordlist.print();
	ordlist.QuickSort(0,ordlist.Length()-1);
	cout<<"已排序表："<<endl;
	ordlist.print();
}