sort.c

这是数据结构的课程设计

/*头文件和宏定义部分*/
#include"string.h"
#include"ctype.h"
#include"time.h"
#include"malloc.h" /* malloc()等 */
#include"limits.h" /* INT_MAX等 */
#include"stdio.h" /* EOF(=^Z或F6),NULL */
#include"stdlib.h" /* atoi() */
#include"io.h" /* eof() */
#include"math.h" /* floor(),ceil(),abs() */
#include"process.h" /* exit() */
/* 函数结果状态代码 */

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MAXSIZE 100   //示例数据类型的最大长度



typedef int KeyType;		//定义关键字类型为整数类型
typedef int InfoType;	//定义关键字类型为整数类型
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef struct{
	KeyType key;	//关键字项
	InfoType otherinfo;		//其它数据项
}RedType;		//记录类型

typedef struct {
	RedType r[MAXSIZE+1];		//r[0]闲置或用作哨兵单元
	int length;		//顺序表长度
}SqList;		//顺序表类型



void InitData(SqList *L,int dataCopy[])
{
	int i;
	L->length=MAXSIZE;
	srand((unsigned)time(NULL)); 
	for(i=0;i<=MAXSIZE;i++)
	{
		L->r[i].otherinfo=0;
		dataCopy[i]=L->r[i].key=rand();
	}
}

void PrintData(SqList L)
{
	int i;
	for(i=1;i<=L.length;i++)
	{
		printf("%d\t",L.r[i].key);
	}
}

void ResumeData(SqList *L,int dataCopy[])
{
	int i;
	for(i=0;i<=MAXSIZE;i++)
	{
		L->r[i].key=dataCopy[i];
	}
}

void PrintStatistic(int *compareCounts,int *moveCounts)
{
	printf("\n\t\t各种排序方法比较结果:\n\n");
	printf("\t\t起泡排序:    比较次数  %d,移动次数  %d\n",compareCounts[0],moveCounts[0]);
	printf("\t\t直接插入排序:比较次数  %d,移动次数  %d\n",compareCounts[1],moveCounts[1]);
	printf("\t\t简单选择排序:比较次数  %d,移动次数  %d\n",compareCounts[2],moveCounts[2]);
	printf("\t\t快速排序:    比较次数  %d,移动次数  %d\n",compareCounts[3],moveCounts[3]);
	printf("\t\t希尔排序:    比较次数  %d,移动次数  %d\n",compareCounts[4],moveCounts[4]);
	printf("\t\t堆排序:      比较次数  %d,移动次数  %d\n",compareCounts[5],moveCounts[5]);
}



/*******************************直接插入排序*******************************/

void InsertSort(SqList *L,int *compareCounts,int *moveCounts )		//直接插入排序
{
	int i,j;		//
	for(i=2;i<=L->length;i++)		//从顺序表的第二个元素开始进行比较
	{
		if(L->r[i].key<L->r[i-1].key)		//将每个元素与它的前一个元素关键字进行比较
		{
			L->r[0]=L->r[i];		//如果关键字比前一个元素关键字小，就将元素复制作为哨兵
			L->r[i]=L->r[i-1];
			(*moveCounts)+=2;		//关键字移动了2次
			j=i-2;		//从要比较的关键字的前第二个记录开始进行比较,然后后移
			while(L->r[0].key<L->r[j].key)
			{
				L->r[j+1]=L->r[j];		//记录后移
				(*moveCounts)++;		//每作一次后移,移动次数加1
				j--;
				(*compareCounts)++;		//每作一次比较，比较次数加1
			}
			L->r[j+1]=L->r[0];		//插入到正确位置
		}
		(*compareCounts)++;
	}
}



/*******************************希尔排序*******************************/

void ShellInsert(SqList *L,int increment,int *compareCounts,int *moveCounts)
{		//对顺序表作一趟希尔插入排序
	int j,n;
	for(j=1+increment;j<=L->length;j++)
	{
		if(L->r[j].key<L->r[j-increment].key)		//将L->[i]插入到有序增量子表
		{
			L->r[0]=L->r[j];		//暂存在L->r[0]
			L->r[j]=L->r[j-increment];
			(*moveCounts)+=2;
			for(n=j-2*increment;n>0&&L->r[0].key<L->r[n].key;n-=increment)
			{
				L->r[n+increment]=L->r[n];		//记录后移，查找插入位置
				(*moveCounts)++;
				(*compareCounts)++;
			}
			L->r[n+increment]=L->r[0];		//插入
			(*moveCounts)++;
		}
		(*compareCounts)++;
	}
}



void ShellSort(SqList *L,int IncreList[],int times,int *compareCounts,int *moveCounts)		//希尔排序
{		//按增量序列Increlist［0.....times-1］对顺序表Ｌ作希尔排序
	int k;		//
	for(k=0;k<times;k++)
	{
		ShellInsert(L,IncreList[k],compareCounts,moveCounts);		//一趟增量为IncreList[k]的插入排序
	}
}



/*******************************起泡排序*******************************/

void BubbleSort(SqList *L,int *compareCounts,int *moveCounts)		//起泡排序
{
	int i,j;
	for(i=1;i<=L->length;i++)
	{
		for(j=L->length;j>i;j--)
		{		//从后往前两两进行比较，将元素关键字小的交换到前面
			if(L->r[j].key<L->r[j-1].key)	
			{
				L->r[0]=L->r[j];
				L->r[j]=L->r[j-1];
				L->r[j-1]=L->r[0];
				(*moveCounts)+=3;
			}
			(*compareCounts)++;
		}
	}
}



/*******************************快速排序*******************************/

int Partition(SqList *L,int low,int high,int *compareCounts,int *moveCounts)		//快速排序中的分
{
	int pivotkey;
	L->r[0]=L->r[low];
	(*moveCounts)++;
	pivotkey=L->r[low].key;
	while(low<high)
	{
		while(low<high&&L->r[high].key>=pivotkey)
		{
			high--;
			(*compareCounts)++;
		}
		L->r[low]=L->r[high];
		(*moveCounts)++;
		while(low<high&&L->r[low].key<=pivotkey)
		{
			low++;
			(*compareCounts)++;
		}
		L->r[high]=L->r[low];
		(*moveCounts)++;
		(*compareCounts)++;
	}
	L->r[low]=L->r[0];
	(*moveCounts)++;
	return low;
}



void QSort(SqList *L,int low,int high,int *compareCounts,int *moveCounts)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=Partition(L,low,high,compareCounts,moveCounts);
		QSort(L,low,pivotloc-1,compareCounts,moveCounts);
		QSort(L,pivotloc+1,high,compareCounts,moveCounts);
	}
}



void QuickSort(SqList *L,int *compareCounts,int *moveCounts)
{
	QSort(L,1,L->length,compareCounts,moveCounts);
}



/*******************************简单选择排序*******************************/

void SelectSort(SqList *L,int *compareCounts,int *moveCounts)
{
	int i,j,minPoint;
	for(i=1;i<=L->length;i++)
	{
		L->r[0]=L->r[i];
		(*moveCounts)++;
		minPoint=i;
		for(j=i+1;j<=L->length;j++)
		{
			if(L->r[j].key<L->r[0].key)
			{
				L->r[0]=L->r[j];
				(*moveCounts)++;
				minPoint=j;
			}
			(*compareCounts)++;
		}
		L->r[minPoint]=L->r[i];
		L->r[i]=L->r[0];
		(*moveCounts)++;
	}
}



/*******************************堆排序*******************************/

void HeapAdjust(SqList *L,int s,int m,int *compareCounts,int *moveCounts)
{
	RedType cmpKey;		//待比较的值
	int j;
	cmpKey=L->r[s];
	(*moveCounts)++;
	for(j=s*2;j<=m;j*=2)
	{
		(*compareCounts)+=2;
		if(j<m&&L->r[j].key<L->r[j+1].key) j++;
		if(!(cmpKey.key<L->r[j].key)) break;
		L->r[s]=L->r[j];
		(*moveCounts)++;
		s=j;		
	}
	L->r[s]=cmpKey;
	(*moveCounts)++;
}



void HeapSort(SqList *L,int *compareCounts,int *moveCounts)
{
	int i;
	RedType temp;
	for(i=L->length/2;i>0;i--)	HeapAdjust(L,i,L->length,compareCounts,moveCounts);
	for(i=L->length;i>1;i--)
	{
		temp=L->r[1];
		L->r[1]=L->r[i];
		L->r[i]=temp;
		(*moveCounts)+=3;
		HeapAdjust(L,1,i-1,compareCounts,moveCounts);
	}
}



void SortCompare()
{
	SqList L;		//用顺序表存放待排序的元素
	int dataCopy[MAXSIZE+1],i;
	int compareCounts[7],moveCounts[7];
	int increList[6];
	for(i=0;i<5;i++)
	{
		increList[i]=(int)pow(2,7-i)-1;
	}
	increList[5]=1;
	for(i=0;i<7;i++)
	{

		compareCounts[i]=0;
		moveCounts[i]=0;
	}
	InitData(&L,dataCopy);		//初始化数据，随机产生100个正整数的数列
	printf("\t\t\t初始化数据后产生的数列:\n");		
	PrintData(L);		//显示出未排序的数列

	printf("\n\n\t\t\t经过起泡排序后产生的数列:\n");
	BubbleSort(&L,&compareCounts[0],&moveCounts[0]);		//对数列使用起泡排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过直接插入排序后产生的数列:\n");
	InsertSort(&L,&compareCounts[1],&moveCounts[1]);		//对数列使用插入排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过简单选择排序后产生的数列:\n");
	SelectSort(&L,&compareCounts[2],&moveCounts[2]);		//对数列使用简单选择排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过快速排序后产生的数列:\n");
	QuickSort(&L,&compareCounts[3],&moveCounts[3]);		//对数列使用快速排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过希尔排序后产生的数列:\n");
	ShellSort(&L,increList,6,&compareCounts[4],&moveCounts[4]);		//对数列使用希尔排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过堆排序后产生的数列:\n");
	HeapSort(&L,&compareCounts[5],&moveCounts[5]);		//对数列使用堆排序
	PrintData(L);		//显示出排序好的数列
	PrintStatistic(compareCounts,moveCounts);
}



main()	
{
	int i,temp;
	for(i=0;i<5;i++)
	{
		SortCompare();
		printf("\n\t\t请按任意键进行下一组数据的排序对比\n\n");
		temp=getchar();
	}
}