排序算法比较1.cpp

内含各种算法的可执行代码。内容简单

#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define Maxsize  80000

typedef struct
{

	int key;

}Redtype;

typedef struct
{

	Redtype r[Maxsize+1];
	
	int length;

}Sqlist;

void Initlist(Sqlist &L,int n)                              //初始化表(参数n为要参加排序的数的个数)
{
	int i;

	srand( (unsigned)time( NULL ) );						//随机产生种子
	
	for(i=1;i<=n;++i)
	
		L.r[i].key=n*rand()/(n+1.0);							// rand()产生伪随机数0 到n
	
	L.length=n+1;
}//Initlist

void Printlist (Sqlist L )

{	
	int i;
	
	printf("排序后的线性表为：\n");
	
	for (i=1;i<L.length;i++)
	
	 printf("%d  ",L.r[i]);

}



void Insertionsort(Sqlist L)                       //直接插入排序（书上的算法）
{
	
	int i,j;
	
	for(i=2;i<L.length;++i)
	
		if(	L.r[i].key<L.r[i-1].key)                //需将L.r[i]插入有序子表
	{
	
			L.r[0]=L.r[i];							//复制为哨兵
	
			L.r[i]=L.r[i-1];						
	
			for(j=i-2;L.r[0].key<L.r[j].key;--j)
		
				L.r[j+1]=L.r[j];					//记录后移
	
			L.r[j+1]=L.r[0];						//插入到正确位置
	
	}
	//Printlist (L);								//测试用

}//InsertSort


void Binsertsort(Sqlist L)                         //折半排序（书上的算法）
{

	int i,j;
	
	int low,high;
	
	for(i=2;i<L.length;++i)
	
	{
		L.r[0]=L.r[i];								//将L.r[i]暂存到L.r[0]
	
		low=1; 
	
		high=i-1;
	
		while(low<=high)							// 在r.[low...high]中折半查找有序插入的位置
	
		{
		
			int m=(low+high)/2;						//折半
			
			if(L.r[0].key<L.r[m].key)				//插入点在低半区
				
				high=m-1;
		
			else									//插入点在高半区
			
				low=m+1;
		}
		
		for(j=i-1;j>=high+1;--j)					
		
			L.r[j+1]=L.r[j];						//记录后移
		
		L.r[high+1]=L.r[0];							//插入

	}

	//Printlist (L);								//测试用

}//Binsertsort


void Electsort(Sqlist L)                        //选择排序
{
	
	int min,j;
	
	for(int i=1;i<L.length-1;i++)                               
	
	{
        
		min=i;
		
		for(j=min+1;j<L.length;j++)
		
			if(L.r[min].key>L.r[j].key)
			
				min=j;
		
			if(min!=i)							//判断min与i是否相等，若＝则说明原假设正确反之交换数值
			{
			
				L.r[0]=L.r[min];
			
				L.r[min]=L.r[i];
			
				L.r[i]=L.r[0];				//L.r[i]作一个temp，
		
			}
	}

	//Printlist (L);								//测试用

}//Electsort


void Bubblesort(Sqlist L)                     //普通冒泡排序
{
	
	int i,j;

	for(i=1;i<L.length;i++)                               //冒泡排序
	
		for(j=1;j<L.length-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];
		
			}

	//Printlist (L);									//测试用					

}//Bubblesort


void Heapadjust(Sqlist &L,int s,int m)			//堆排序中的筛选
{
	
	int j,rc;

	rc=L.r[s].key;
	
	for(j=s*2;j<=m;j*=2)						//沿key较大的孩子节点向下筛选
	
	{
		if(j<m && L.r[j].key<=L.r[j+1].key)		//j为key较大的记录下标
		
			++j;
		
		if(rc>L.r[j].key)				//L.r[0]应当插入在位置s上
		
			break;
	
		L.r[s]=L.r[j];

		s=j;

	}

	L.r[s].key=rc;								//插入
}


void Heapsort(Sqlist &L)                //堆排序（书上算法）
{
	
	int i,t;
	
	for(i=L.length/2;i>0;--i)
	
		Heapadjust(L,i,L.length);
	
	for(i=L.length;i>1;--i)
	
	{
	
		t=L.r[1].key;
	
		L.r[1].key=L.r[i].key;
	
		L.r[i].key=t;
	
		Heapadjust(L,1,i-1);
	}

//	Printlist (L);									//测试用

}//Heapsort


int Partition(Sqlist &L,int low,int high)

{	
	int pivotkey;
	
	L.r[0]=L.r[low];
	
	pivotkey=L.r[low].key;
	
	while(low<high)
	{
		while(low<high&&L.r[high].key>=pivotkey) 
		{--high;
		
		L.r[low]=L.r[high];}
		
		while(low<high&&L.r[low].key<=pivotkey) {++low;

		L.r[high]=L.r[low];}
	}

	L.r[low]=L.r[0];

	return low;

}//Partition;

void Quicksort(Sqlist &L,int low,int high)
{
	int pivotloc;
	
	if (low<high)

	{ 
	pivotloc=Partition(L,low,high);
 
	Quicksort(L,low,pivotloc-1);
 
	Quicksort(L,pivotloc+1,high);
	
	}

}//Quicksort



void main()
{
	Sqlist List;

	clock_t starttime;									//开始计时的变量
	
	clock_t endtime;								    //结束计时的变量
	
	int totaltime1,totaltime2,totaltime3,totaltime4,
		
	totaltime5,totaltime6,totaltime7;									//计时变量
    
	int  i,number;									    //排序数的个数
    
	char ch,ch1,ch2;
	
	printf("**********************************************************\n");

	printf("\n欢迎使用本排序程序\n");

	printf("\n对随机数进行排序并计算各种排序所耗时间请按任意键...\n");

	printf("\n退出本程序请按0...\n");

	printf("\n**********************************************************\n");

	scanf("%c",&ch);

	if (ch=='0')
	
	{	exit(0);
	
		printf("\n感谢您的使用!!!\n");
	}

	else
	{
		printf("输入要随机排序数的个数:   ");
	
		scanf("%d", &number);
	
		printf("\n请稍后...正在计算排序时间...\n");

		Initlist(List,number);

		starttime=clock();								    //直接插入排序
	
		Insertionsort(List);
	
		endtime=clock();
	
		totaltime1=endtime-starttime;
	
		starttime=clock();									//折半插入排序
	
		Binsertsort(List);

		endtime=clock();
	
		totaltime2=endtime-starttime;
	
		starttime=clock();									//选择排序
	
		Electsort(List); 
	
		endtime=clock();

		totaltime3=endtime-starttime;
	   
		starttime=clock();									//冒泡排序
    
		Bubblesort(List); 
	
		endtime=clock();
	
		totaltime4=endtime-starttime;

		starttime=clock();									//堆排序
   
		Heapsort(List); 
	
		endtime=clock();

		totaltime5=endtime-starttime;
	
		starttime=clock();									//快速排序
    
		Quicksort(List,1,List.length-1); 

		endtime=clock();
	
		totaltime6=endtime-starttime;
	
		printf("\n“直接插入排序”的时间是:  %d ms \n",totaltime1);
	
		printf("\n“折半插入排序”的时间是:  %d ms \n",totaltime2);
	
		printf("\n“选择排序”的时间是:  %d ms \n",totaltime3);
	
		printf("\n“普通冒泡排序”的时间是:  %d ms\n",totaltime4);
	
		printf("\n“堆排序”的时间是:  %d ms\n",totaltime5);
	
		printf("\n“快速排序”的时间是:  %d ms\n",totaltime6);	
	
		printf("\n是否需要打印出排序后的随机序列？(Y/N)\n");
	
		scanf("%s",&ch1);
	
		if(ch1=='Y'||ch1=='y')
		
		{	Printlist (List);
			
			printf("\n排序成功!!!\n");

			printf("\n感谢您的使用!!!\n");
		}
	
		else if (ch1=='N'||ch1=='n')

		{	printf("\n感谢您的使用!!!\n");
		
			exit(0);
		
		}
		else
		{
			printf("输入有误!!!\n");

			printf("\n如需重新排列请输入1；\n");
		
			printf("\n如要退出该程序请出入0；\n");

			scanf("%c",&ch2);

			if(ch2=='1')
			
			{
				Quicksort(List,1,List.length-1); 
		
				Printlist (List);

				printf("\n感谢您的使用!!!\n");
			}

			else if (ch2=='0')
			
			{	printf("\n感谢您的使用!!!\n");
				
				exit(0);
			}

			else 

			{	printf("输入有误!!!");
				
				printf("\n感谢您的使用!!!\n");
			}
		}	

	}
	
}