交换排序

//冒泡排序算法
#include "seqlist.cpp"
 
void BubbleSort(RecType R[],int n)
{
	int i,j,k;
	RecType tmp;
	for (i=0;i<n-1;i++) 
	{
		for (j=n-1;j>i;j--)	//比较,找出本趟最小关键字的记录
			if (R[j].key<R[j-1].key)   
			{
				tmp=R[j];  //R[j]与R[j-1]进行交换,将最小关键字记录前移
				R[j]=R[j-1];
				R[j-1]=tmp;
			}
		printf("  i=%d: ",i);
		DispList(R,n);
	}
} 
int main()
{
	int n=10;
	RecType R[MAXL];
	KeyType a[]={9,8,7,6,5,4,3,2,1,0};
	CreateList(R,a,n);
	printf("排序前:"); DispList(R,n);
	BubbleSort(R,n); 
	printf("排序后:"); DispList(R,n);
	return 1;
}

//改进的冒泡排序算法
#include "seqlist.cpp"
 
void BubbleSort1(RecType R[],int n)
{	int i,j;
	bool exchange;
	RecType tmp;
	for (i=0;i<n-1;i++) 
	{	exchange=false;					//一趟前exchange置为假
		for (j=n-1;j>i;j--)				//归位R[i],循环n-i-1次
			if (R[j].key<R[j-1].key)	//相邻两个元素反序时
			{	tmp=R[j];				//将这两个元素交换
				R[j]=R[j-1];
				R[j-1]=tmp;
				exchange=true;			//一旦有交换，exchange置为真
			}
		printf("  i=%d: ",i);
		DispList(R,n);
		if (!exchange)					//本趟没有发生交换，中途结束算法
			return;
	}
}
 
int main()
{
	int n=10;
	RecType R[MAXL];
	KeyType a[]={0,1,7,2,5,4,3,6,8,9};
	CreateList(R,a,n);
	printf("排序前:"); DispList(R,n);
	BubbleSort1(R,n);  
	printf("排序后:"); DispList(R,n);
	return 1;
}

//快速排序算法
#include "seqlist.cpp"
int count=0;
int partition(RecType R[],int s,int t)	//一趟划分
{
	int i=s,j=t;
	RecType tmp=R[i];			//以R[i]为基准
	while (i<j)  				//从两端交替向中间扫描,直至i=j为止
	{	while (j>i && R[j].key>=tmp.key)
			j--;				//从右向左扫描,找一个小于tmp.key的R[j]
		R[i]=R[j];				//找到这样的R[j],放入R[i]处
		while (i<j && R[i].key<=tmp.key)
			i++;				//从左向右扫描,找一个大于tmp.key的R[i]
		R[j]=R[i];				//找到这样的R[i],放入R[j]处
	}
	R[i]=tmp;
	return i;
}
void QuickSort(RecType R[],int s,int t) //对R[s..t]的元素进行快速排序
{	int i;
	RecType tmp;
	if (s<t) 					//区间内至少存在两个元素的情况
	{	count++;
		i=partition(R,s,t);
		DispList(R,10);			//调试用
		QuickSort(R,s,i-1);		//对左区间递归排序
		QuickSort(R,i+1,t);		//对右区间递归排序
	}
}
/*
int main()
{
	int i,n=10;
	RecType R[MAXL];
	KeyType a[]={15,18,29,12,35,32,27,23,10,20};
	CreateList(R,a,n);
	printf("排序前:"); DispList(R,n);
	QuickSort(R,0,n-1);
	printf("排序后:"); DispList(R,n);
	return 1;
}
*/
 
int main()
{
	int i,n=10;
	RecType R[MAXL];
	KeyType a[]={6,8,7,9,0,1,3,2,4,5};
	CreateList(R,a,n);
	printf("排序前:"); DispList(R,n);
	QuickSort(R,0,n-1);
	printf("排序后:"); DispList(R,n);
	printf("count=%d\n",count);
	return 1;
}