sort.cpp

数据结构实验

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <windows.h>

#define MAXSIZE 300
#define LT(key1,key2) ((key1)<(key2))

typedef int  KeyType;
typedef int* InfoType;

typedef struct
{
	KeyType  key;
	InfoType otherinfo;
}RedType;

typedef struct
{
	RedType r[MAXSIZE+1];
	int length;
}SqList;

void HeapSort(SqList L);
void print(SqList L);
void InsertSort(SqList L);
void BInsertSort(SqList L);
void ShellInsertSort(SqList &L,int dk,int &times,int &changes);
void ShellSort(SqList L);
void ShellInsertSort(SqList &L,int dk,int &times,int &changes);
void ShellSort(SqList L);
void BubbleSort(SqList L);
int Partition(SqList &L,int low,int high,int &times,int &changes);
void QSort(SqList &L,int low,int high,int &times,int &changes);
void QuickSort(SqList L);
int SelectMinKey(SqList L,int i,int &times);
void SelectSort(SqList L);
void HeapAdjust(SqList &L,int s,int m,int &times,int &changes);

void main()
{
Z:	printf("***********************************************************\n");
    printf("***              ^_^  内部排序算法比较  ^_^             ***\n");
	printf("***********************************************************\n");
	SqList L,G;
	L.length=10;
	int i;
B:	printf("输入有序表长度length:");
	scanf("%d",&L.length);
	if(L.length>300)
		L.length=300;
	printf("\n***********************************************************\n");
	printf("***    将随机产生一组Size=%3d的数据，确定 ?   ---y/n--  ***\n",L.length);
	getchar();
	if(getchar()!='y')
		goto B;
	for(i=1;i<=L.length;i++)
		L.r[i].key=rand();

	for(i=0;i<4;i++)
	{
		_sleep(200);
		system("cls");
	//	printf("***********************************************************\n");
		printf("***********************************************************\n");
		printf("***            随机数据生成中      请等待.              ***\n");
		printf("***********************************************************\n");
		_sleep(200);
		system("cls");
	//	printf("***********************************************************\n");
		printf("***********************************************************\n");
		printf("***            随机数据生成中      请等待..             ***\n");
		printf("***********************************************************\n");
		_sleep(200);
		system("cls");
//		printf("***********************************************************\n");
		printf("***********************************************************\n");
		printf("***            随机数据生成中      请等待...            ***\n");
		printf("***********************************************************\n");
	}

	system("cls");
//	for(i=1;i<=L.length;i++)
//		scanf("%d",&L.r[i].key);
	printf("随机生成的序列:");
	print(L);
	printf("\n排序后的的序列:");
	G=L;
//	printf("\n起泡排序排序");
	BubbleSort(L);
	L=G;
//	printf("直接插入排序");
	InsertSort(L);
	L=G;
//	printf("\n折半插入排序");
	BInsertSort(L);
	L=G;
//	printf("\n简单选择排序");
	SelectSort(L);
	L=G;
//	printf("\n快速排序");
	QuickSort(L);
	L=G;
//	printf("\n希尔排序排序");
	ShellSort(L);
	L=G;
//	printf("\n堆排序排序");
	HeapSort(L);

	printf("***********************************************************\n");
	printf("***            Continue  or  Quit  ?     c/q            ***\n");
	getchar();
	if(getchar()=='c')
	{
		system("cls");
		goto Z;
	}
	printf("***       ^_^ Welcome to use again ^_^                  ***\n");
}

void print(SqList L)
{
	int i;
	printf("\n");
	for(i=1;i<=L.length;i++)
	{
		printf("[%3d] %5d  ",i,L.r[i].key);
		if(!(i%6))printf("\n");
	}
}//print

void InsertSort(SqList L)
{
	int i,j,times=0,changes=0;
	for(i=2;i<=L.length;++i)
	{
		if(LT(L.r[i-1].key,L.r[i].key))
		{
			L.r[0].key=L.r[i].key;
			L.r[i]=L.r[i-1];
			for(j=i-2;LT(L.r[j].key,L.r[0].key);--j,times++)
			{
				L.r[j+1].key=L.r[j].key;
				changes++;
			}
			L.r[j+1].key=L.r[0].key;
			changes++;
		}
		times++;
	}
	printf("\nInsertSort:\tcompcount=%6d\tshiftcount=%6d\n\n",times,changes);
//	print(L);
}//InsertSort

void BInsertSort(SqList L)//折半插入排序
{
	int i=0,j=0,times=0,changes=0;
	int low=0,high=0;
	int m=0;
	for(i=2;i<=L.length;++i)
	{
		L.r[0].key=L.r[i].key;
		low=1;high=i-1;
		while(low<=high)
		{
			m = (low+high)/2;
			if(LT(L.r[m].key,L.r[0].key))high=m-1;
			else low = m+1;
			times++;
		}
		for(j=i-1;j>=high+1;--j)
		{
			L.r[j+1].key = L.r[j].key;
			changes++;
		}
		L.r[high+1].key = L.r[0].key;
		changes++;
	}
 	printf("\nBInsertSort:\tcompcount=%6d\tshiftcount=%6d\n\n",times,changes);
//	print(L);
}//BInsertSort

void ShellInsertSort(SqList &L,int dk,int &times,int &changes)
{
	int i,j;
	for(i=dk+1;i<=L.length;++i)
	{
		if(LT(L.r[i-dk].key,L.r[i].key))
		{
			L.r[0].key = L.r[i].key;
			changes++;
			for(j=i-dk;j>0 && LT(L.r[j].key,L.r[0].key);j-=dk)
			{
				L.r[j+dk].key=L.r[j].key;
				times++;
				changes++;
			}
			L.r[j+dk].key=L.r[0].key;
			changes++;
		}
		times++;
	}
}//ShellInsertSort

void ShellSort(SqList L)
{
	int k,times=0,changes=0;
	double t;
	t=log(L.length)/log(2);
	for(k=1;k<=t;k++)
		ShellInsertSort(L,(int)pow(2,t-k+1)-1,times,changes);
	printf("\nShellSort:\tcompcount=%6d\tshiftcount=%6d\n\n",times,changes);
//	print(L);
}//ShellSort

void BubbleSort(SqList L)
{
	int temp,times=0,changes=0;
	for(int i=0;i<L.length-1;i++)
	{
		for(int j=1;j<L.length-i;j++)
		{
			if(LT(L.r[j].key,L.r[j+1].key))
			{
				temp=L.r[j+1].key;
				L.r[j+1].key=L.r[j].key;
				L.r[j].key=temp;
				changes+=3;
			}
			times++;
		}
	}
	print(L);
	printf("\nBubbleSort:\tcompcount=%6d\tshiftcount=%6d\n\n",times,changes);
}//BubbleSort

int Partition(SqList &L,int low,int high,int &times,int &changes)
{
	L.r[0].key=L.r[low].key;
	changes++;
	while(low<high)
	{
		while((low<high) && !(LT(L.r[0].key,L.r[high].key)))
		{
			--high;
			times++;
		}
		L.r[low].key=L.r[high].key;
		while((LT(L.r[0].key,L.r[low].key)) && (low<high))
		{
			low++;
			times++;
		}
		L.r[high].key=L.r[low].key;
		changes+=2;
	}
	L.r[low].key=L.r[0].key;
	changes++;
	return low;
}//Partition

void QSort(SqList &L,int low,int high,int &times,int &changes)
{
	int pivotloc=0;
	if(low<high)
	{
		pivotloc=Partition(L,low,high,times,changes);
		QSort(L,low,pivotloc-1,times,changes);
		QSort(L,pivotloc+1,high,times,changes);
	}
}//QSort

void QuickSort(SqList L)
{
	int times=0,changes=0;
	QSort(L,1,L.length,times,changes);
	printf("\nQuickSort:\tcompcount=%6d\tshiftcount=%6d\n\n",times,changes);
//	print(L);
}//QuickSort

int SelectMinKey(SqList L,int i,int &times){
	int m=i;
	int n;
	for(n=i;n<=L.length;n++){
		if(!LT(L.r[n].key,L.r[m].key))
			m=n;
		times++;
	}
	return m;
}//SelectMinKey

void SelectSort(SqList L)
{
	int i=0,j=0,times=0,changes=0;
	for(i=1;i<L.length;i++)
	{
		j=SelectMinKey(L,i,times);
		if(i!=j){
			L.r[0]=L.r[i];
			L.r[i]=L.r[j];
			L.r[j]=L.r[0];
			changes+=3;
		}
	}
	printf("\nSelectSort:\tcompcount=%6d\tshiftcount=%6d\n\n",times,changes);
//	print(L);
}//SelectSort


void HeapAdjust(SqList &L,int s,int m,int &times,int &changes)

{
	int j;
	L.r[0].key=L.r[s].key;
	for(j=2*s;j<=m;j*=2)
	{
		if(j<m && LT(L.r[j+1].key,L.r[j].key))
			++j;
		times+=2;
		if(!LT(L.r[j].key,L.r[0].key))
			break;
		L.r[s].key=L.r[j].key;
		s=j;
		changes++;
	}
	L.r[s].key=L.r[0].key;
	changes++;
}//HeapAdjust

void HeapSort(SqList L)
{
	int length=L.length-1;
	int i,times=0,changes=0;
	for(i=length/2;i>0;--i)
		HeapAdjust(L,i,length,times,changes);
	for(i=length+1;i>1;--i)
	{
		L.r[0].key=L.r[1].key;
		L.r[1].key=L.r[i].key;
		L.r[i].key=L.r[0].key;
		changes+=3;
		HeapAdjust(L,1,i-1,times,changes);
	}
	printf("\nHeapSort:\tcompcount=%6d\tshiftcount=%6d\n\n",times,changes);
//	print(L);
}//HeapSort