mode.cpp

各种内部排序算法的实现和比较

#include "base.h"
#include "GetTime.h"

int  InitSqList		(SqList &L);						//初始化线形表L
int  ClearSqList	(SqList &L);						//将存在的线形表L置空
int	 DestroySqList	(SqList &L);						//销毁线形表L
int	 InitSLinkList	(SLinkListType &SL);				//初始化静态链表SL
int  ClearSLinkList	(SLinkListType &SL);				//将存在的静态链表SL置空
int  DestroySLinkList(SLinkListType &SL);				//销毁静态链表SL
int  InitSLList		(SLList &SLL,RedType D[],int n);	//初始化静态链表SLL
int	 ClearSLList	(SLList &SLL);						//将存在的静态链表SLL置空
int  DestroySLList	(SLList &SLL);						//销毁静态链表SLL
void PrintSqList	(SqList L );						//输出线性表L元素
//	void CreatSqList	(SqList &L);						//建线性表L(测试用)
void PrintSLinkList	(SLinkListType SL);					//输出静态链表SL元素
//	void CreatSLinkList	(SLinkListType &SL);				//建静态链表SL(测试用)
//	void PrintSLList	(SLList SLL);						//数组输出静态链表SLL元素
//	void PrintlSLList	(SLList SLL);						//链表输出SLL链表元素
void ReadFile(SqList &L,char *p);
void ReadFile(SLinkListType &SL,char *p);
void ReadFile(RedType D[],int &length,char *p);
void WriteFile(SqList L,char *q);
void WriteFile(SLinkListType SL,char *q);
void WriteFile(SLList SLL,char *q);

void InsertSort		(SqList &L);					//直接插入排序
void BInsertSort	(SqList &L);					//折半插入排序
void TwoInsertSort	(SqList &L);					//2-路插入排序
void SInsertSort	(SLinkListType &SL);			//表插入排序
void ShellSort		(SqList &L,int dlta[],int t);	//希尔排序
void BubbleSort		(SqList &L);					//冒泡排序
void QuickSort		(SqList &L);					//快速排序
void SelectSort		(SqList &L);					//简单选择排序
void HeapSort		(HeapType &H);					//堆排序
void MergeSort		(SqList &L);					//归并排序
void RadixSort		(SLList &L);					//基数排序

void Insort(float &tI,int flag)
{
	SqList	L;
	int  i;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSqList(L);
	cout<<"直接插入排序开始!"<<endl;
	for(i=0,tI=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSqList(L);
		ReadFile(L,p);
		cout<<"从文件"<<p<<"中读取数据,直接插入排序中..."<<endl;
		t1=getTime();
		InsertSort(L);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tI+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(L,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n直接插入排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tI/10<<"s"<<endl;
	DestroySqList(L);
}/////////////////// Insort

void BInsort(float &tBI,int flag)
{
	SqList	L;
	int  i;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSqList(L);
	cout<<"折半插入排序开始!"<<endl;
	for(i=0,tBI=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSqList(L);
		ReadFile(L,p);
		cout<<"从文件"<<p<<"中读取数据,折半插入排序中..."<<endl;
		t1=getTime();
		BInsertSort(L);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tBI+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(L,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n折半插入排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tBI/10<<"s"<<endl;
	DestroySqList(L);
}////////////////////// BInsort

void TInsort(float &tT, int flag)
{
	SqList	L;
	int  i;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSqList(L);
	cout<<"2-路插入排序开始!"<<endl;
	for(i=0,tT=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSqList(L);
		ReadFile(L,p);
		cout<<"从文件"<<p<<"中读取数据,2-路插入排序中..."<<endl;
		t1=getTime();
		BInsertSort(L);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tT+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(L,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n2-路插入排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tT/10<<"s"<<endl;
	DestroySqList(L);
}////////////////////// TInsort

void SInsort(float &tSI, int flag)
{
	SLinkListType SL;
	int  i;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSLinkList(SL);
	cout<<"表插入排序开始!"<<endl;
	for(i=0,tSI=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSLinkList(SL);
		ReadFile(SL,p);
		cout<<"从文件"<<p<<"中读取数据,表插入排序中..."<<endl;
		t1=getTime();
		SInsertSort(SL);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tSI+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(SL,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n表插入排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tSI/10<<"s"<<endl;
	DestroySLinkList(SL);
}/////////////////////// SInsort

void ShInsort(float &tSh,int flag)
{
	SqList L;
	int  i;
	float t1,t2;
	int  t=10;
	int  a[10]={100,80,60,40,20,10,8,5,2,1};
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSqList(L);
	cout<<"希尔排序开始!"<<endl;
	for(i=0,tSh=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSqList(L);
		ReadFile(L,p);
		cout<<"从文件"<<p<<"中读取数据,希尔排序中..."<<endl;
		t1=getTime();
		ShellSort(L,a,t);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tSh+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(L,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n希尔排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tSh/10<<"s"<<endl;
	DestroySqList(L);
}///////////////////////// ShInsort

void Busort(float &tBu,int flag)
{
	SqList L;
	int  i;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSqList(L);
	cout<<"冒泡排序开始!"<<endl;
	for(i=0,tBu=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSqList(L);
		ReadFile(L,p);
		cout<<"从文件"<<p<<"中读取数据,冒泡排序中..."<<endl;
		t1=getTime();
		BubbleSort(L);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tBu+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(L,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n冒泡排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tBu/10<<"s"<<endl;
	DestroySqList(L);
}////////////////////////// Busort

void Qsort(float &tQ,int flag)
{
	SqList L;
	int  i;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSqList(L);
	cout<<"快速排序开始!"<<endl;
	for(i=0,tQ=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSqList(L);
		ReadFile(L,p);
		cout<<"从文件"<<p<<"中读取数据,快速排序中..."<<endl;
		t1=getTime();
		QuickSort(L);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tQ+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(L,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n快速排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tQ/10<<"s"<<endl;
	DestroySqList(L);
}///////////////////////// Qsort

void Ssort(float &tSe,int flag)
{
	SqList L;
	int  i;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSqList(L);
	cout<<"简单选择排序开始!"<<endl;
	for(i=0,tSe=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSqList(L);
		ReadFile(L,p);
		cout<<"从文件"<<p<<"中读取数据,简单选择排序中..."<<endl;
		t1=getTime();
		SelectSort(L);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tSe+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(L,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n简单选择排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tSe/10<<"s"<<endl;
	DestroySqList(L);
}////////////////////////// Ssort

void Hsort(float &tH,int flag)
{
	HeapType H;
	int  i;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSqList(H);
	cout<<"堆排序开始!"<<endl;
	for(i=0,tH=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSqList(H);
		ReadFile(H,p);
		cout<<"从文件"<<p<<"中读取数据,堆排序中..."<<endl;
		t1=getTime();
		HeapSort(H);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tH+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(H,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n堆序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tH/10<<"s"<<endl;
	DestroySqList(H);
}////////////////////////// Hsort

void Msort(float &tM,int flag)
{
	SqList L;
	int  i;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	InitSqList(L);
	cout<<"归并排序开始!"<<endl;
	for(i=0,tM=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSqList(L);
		ReadFile(L,p);
		cout<<"从文件"<<p<<"中读取数据,归并排序中..."<<endl;
		t1=getTime();
		MergeSort(L);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tM+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(L,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n归并排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tM/10<<"s"<<endl;
	DestroySqList(L);
}////////////////////////// Msort

void Rsort(float &tR,int flag)
{
	SLList SLL;
	RedType D[MAX_SPACE];
	int  i;
	int  length;
	float t1,t2;
	char choice;
	char *p,*q;
	char namer[6]={'a','.','t','x','t'};
	char namew[7]={'a','o','.','t','x','t'};

	cout<<"基数排序开始!"<<endl;
	for(i=0,tR=0;i<NUM;i++)
	{
		p=&namer[0];
		q=&namew[0];

		if(i!=0)
			ClearSLList(SLL);
		length=0;
		ReadFile(D,length,p);
		InitSLList(SLL,D,length);
		cout<<"从文件"<<p<<"中读取数据,基数排序中..."<<endl;
		t1=getTime();
		RadixSort(SLL);
		t2=getTime();
		
		cout.precision(6);
		cout.setf(ios::fixed|ios::right|ios::showpoint);
		cout<<"本次用时:  ";
		cout.width(10);
		cout<<t2-t1<<"s"<<endl;
		tR+=(t2-t1);
		if(flag==1)
		{
			cout<<"需要将排序后的数据写进文件吗?('Y'/'N')"<<endl;
			cin >>choice;
			if(choice=='y'||choice=='Y')
			{
				WriteFile(SLL,q);
				cout<<"数据已写入"<<q<<"文件中!"<<endl;
			}
		}
		namer[0]+=1;
		namew[0]+=1;
	}
	cout<<"\n基数排序结束!"<<endl;
	cout.precision(6);
	cout.setf(ios::fixed|ios::right|ios::showpoint);
	cout<<"平均用时:";
	cout.width(10);
	cout<<tR/10<<"s"<<endl;
	DestroySLList(SLL);
}////////////////////////// Rsort