排序算法比较未完成.cpp

排序算法比较排序算法排序算法比较排序算法比较

/*
题目：2、排序算法比较 （必做）
设计要求：利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，…,30000），
利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法
（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间。
时间：2008年1月6日   作者：付斌   学号：040640319*/
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define Maxsize  50000

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("排序后的线性表为：");
	
	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);								//测试用

}//Insert_Sort


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);								//测试用

}//Binsert_sort


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);								//测试用

}//Elect_sort


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);									//测试用					

}//Bubble_sort


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]=L.r[i];
	
		L.r[i].key=t;
	
		Heapadjust(L,1,i-1);
	}

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

}//Heap_sort


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;								    //结束计时的变量
	
	double totaltime1,totaltime2,totaltime3,totaltime4,
		
	totaltime5,totaltime6,totaltime7;									//计时变量
    
	int  i,number;									    //排序数的个数
    
	char ch;

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

	Initlist(List,number);

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

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

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

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

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

	endtime=clock();
	
	totaltime6=(double)(endtime-starttime)/1000;
	
	printf("\n“直接插入排序”的时间是:  %f s \n\n",totaltime1);
	
	printf("\n“折半插入排序”的时间是:  %f s \n\n",totaltime2);
	
	printf("\n“选择排序”的时间是:  %f s \n\n",totaltime3);
	
	printf("\n“普通冒泡排序”的时间是:  %f s\n \n",totaltime4);
	
	printf("\n“堆排序”的时间是:  %f s\n \n",totaltime5);
	
	printf("\n“快速排序”的时间是:  %f s\n \n",totaltime6);	
	
	printf("是否需要打印出排序后的随机序列？(Y/N)\n");
	
	scanf("%s",&ch);
	
	if(ch=='Y'||ch=='y')
		
		Printlist (List);
	
	else
	{
		printf("如需从新排列请输入1；\n");
		
		printf("如要退出该程序请出入0；\n");

		scanf("%s",&ch);

		if(ch=='1')
	
	
	}

}