main.cpp

各种排序方法源码

//排序算法验证及评价(排序器)
//以下六种排序算法的实现，将给定的不同规模大小的数据文件进行排序
//1）、Shell排序；				2）、Quick排序
//3）、锦标赛排序；			    4）、堆排序
//5）、归并排序；				6）、基数排序
//在实现排序算法1）~4）时，同时统计数据元素比较的次数和交换的次数，
//进而对这四种算法在特定数据条件下的效率进行分析和评判。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef struct  //存放数据及其出现次数
{
	int data;
	char c[5];  //出现次数最大999次
}node;
#include"shell.h"   //希尔排序头文件
#include"quick.h"   //快速排序头文件
#include"heapsort.h"    //堆排序头文件
#include"merge.h"      //归并排序头文件
#include"radix.h"     //基数排序头文件
#include"treesort.h"   //锦标赛排序(树形选择排序)头文件
#define SIZE 50000
void main()
{
	node *d,*rs;   //d中存储最初读入的数据
	char fn[15],ft[15],c='a';   //数据来源及结果存放文件名存放数组
	int i=0;
	FILE *fp,*fpt;   //数据来源及结果存放文件指针
	int size;
	int *r,n=0;
	int max=-1;     //记录数据中的最大值
	int num,jc=0,bc=0;   //num数据个数，jc交换次数，bc比较次数
	printf(" ***----------------------------排序算法验证及评价--------------------------***\n");
	printf("                   s:Shell排序                     q:Quick排序                 \n");
	printf("                   t:锦标赛排序                    h:堆排序                    \n");
	printf("                   m:归并排序                      r:基数排序                  \n"); 
	printf("                   n:退出                                                      \n"); 
	printf(" ***------------------------------------------------------------------------***\n");
	printf(" 请输入排序方法:");
	c=getchar();
	   while(c!='n')
	   {
		   jc=bc=0;              //交换次数,比较次数清零
		   printf(" 请输入排序前数据存储文件名:");   //来源文件名输入
		   scanf("%s",fn);
		   d=(node *)malloc((SIZE+1)*sizeof(node));    //开辟存储空间
		   size=SIZE;
		   if((fp=fopen(fn,"r"))==NULL)     //打开读文件
		   {
			   printf("can not open %s file.\n",fn);
			   exit(0);
		   }
		   max=-1;
		   num=0;       //记录个数清零
		   while(!feof(fp))   //读入数据
		   {
			   num++;
			   if(num>=size)   //空间不足，重新分配
			   {
                d=(node *)realloc(d,(size*2+1)*sizeof(node));
				size*=2;
			   }
			   fscanf(fp,"%d%s",&d[num].data,d[num].c);
			   if(max<d[num].data)
				   max=d[num].data;
		   }
		   num--;
		   printf(" 读数据完毕\n");
		   printf(" 数据元素个数:%d\n",num);
		   switch(c)    //选择排序方法
		   {
		   case 's':dlta(d,num,jc,bc);      //Shell排序
			   printf(" 比较次数:%d    \n 交换次数:%d\n",bc,jc);break;
		   case 'q':quicksort(d,1,num,jc,bc);    //Quick排序 
			   printf(" 比较次数:%d    \n 交换次数:%d\n",bc,jc);break;
		   case 'h':heapsort(d,num,jc,bc);        //堆排序 
			   printf(" 比较次数:%d    \n 交换次数:%d\n",bc,jc);break;
		   case 'm':mergesort(d,num);break;    //归并排序  
		   case 'r':r=(int*)malloc((num+1)*sizeof(int));   //基数排序 
			   radixsort(d,num,r,max); 
			   break;
		   case 't':rs=(node *)malloc((num+1)*sizeof(node));  //锦标赛排序
			   treesort(d,rs,num,jc,bc);
			   printf(" 比较次数:%d    \n 交换次数:%d\n",bc,jc);break;
		   }
		   printf(" 排序完毕\n");
		   printf(" 请输入排序后数据存储文件名:");   
		   scanf("%s",ft);    //结果存储文件名输入
		   if((fpt=fopen(ft,"w"))==NULL)        //打开写文件
		   {
			   printf("can not open %s file.\n",ft);
			   exit(0);
		   }
		   if(c=='r')   //基数排序按静态指针输出
		   {
			   i=r[0];
			   do
			   {
				   fprintf(fpt,"%d %s\n",d[i].data,d[i].c);
				   i=r[i];
			   }while(i);
			   free(r);   //空间释放
		   }
		   else
			   for(i=1;i<=num;++i)    //排序后数组输出
				   fprintf(fpt,"%d %s\n",d[i].data,d[i].c);
			   free(d);     //空间释放
			   fclose(fp);   //文件关闭
			   fclose(fpt);   //文件关闭
			   printf(" 写数据完毕\n");
			   n++;
        printf(" ***------------------------------------------------------------------------***\n");
		if(n==2)
		   {
			printf("\n\n");
    printf(" ***----------------------------排序算法验证及评价--------------------------***\n");
	printf("                   s:Shell排序                     q:Quick排序                 \n");
	printf("                   t:锦标赛排序                    h:堆排序                    \n");
	printf("                   m:归并排序                      r:基数排序                  \n"); 
	printf("                   n:退出                                                      \n"); 
	printf(" ***------------------------------------------------------------------------***\n");
	n=0;
		   }
			   printf(" 请输入排序方法:");  
			   c=getchar();
			   c=getchar();   //下一个排序
	   }
}