冒泡排序.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
typedef int InfoType;
typedef enum {FALSE,TRUE} Boolean;


#define n 10					//假设的文件长度，即待排序的记录数目
typedef int KeyType;			//假设的关键字类型
typedef struct {				//记录类型
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据项，类型InfoType依赖于具体应用而定义
} RecType;
typedef RecType SeqList[n+1];	//SeqList为顺序表类型，表中第0个单元一般用作哨兵

void main()
{
	void BubbleSort(SeqList R);
	int i;
	SeqList R;
	printf("请输入欲排序的数：");
	for (i=1;i<=n;i++)
		scanf("%d",&R[i].key);
	printf("排序前：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	BubbleSort(R);
	printf("排序后：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}

void BubbleSort(SeqList R)
{	//R[1..n]是待排序的文件，采用自下而上扫描对R做冒泡排序
	int i,j;
	Boolean exchange;				//交换标志
	for(i=1;i<n;i++){				//最多做n-1趟排序
		exchange=FALSE;				//本趟排序开始前，交换标志应为假
		for(j=n-1;j>=i;j--)			//对当前无序区R[i..n]自下向上扫描
			if(R[j+1].key<R[j].key){//交换记录
				R[0]=R[j+1];		//R[0]不是哨兵，仅做暂存单元
				R[j+1]=R[j];
				R[j]=R[0];
				exchange=TRUE;		//发生了交换，故将交换标志置为真
			}
		if(!exchange)				//本趟排序未发生交换，提前终止算法
			return;
	}
}