1问题要求及任务描述.DOC

1、1 问题要求及任务描述1.1 题目要求利用随机函数产生 N 个随机整数（20000 以上） ，对这些数进行多种方法进行排序。要求：1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序） 。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比） ，找出其中两种较快的方法。3)如果采用 4 种或 4 种以上的方法者，可适当加分。1.2 主要任务分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。从时间的角度来分析各种排序的性能。通过测试多组数据来掌握各种排序的方法及适用

2、场合，并能在解决实际问题灵活运用。在编写代码的时候，有以下几个问题：（1）建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环使用系统。（2）分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。（3）通过冒泡排序法来测试每组数据用那种排序算法最优。2 解决问题的主要思路和方法2.1 关键问题核心问题: 排列组合数据模型（逻辑结构）：30000 个随机数存储结构: 保存在不同的文件核心算法: 直接插入、直接选择、冒泡、快速排序、堆排序的算法输入数据: 初始化数组：rand()%50000+1 输出数据：排序内容到文件，排序所用时间2.2 拟采用解决问题的方法把

3、程序分为多个模块，有的是排序的算法如：void InsertSort(int a,int p)，有的是计算排序所用时间的函数如：double TInsertSort(int a,int p)，还有显示菜单的模块void menu()和显示排序结果模块 void Disp(int a)等等，各个模块之间可以互相调用，节省了资源。用 case 作为各个功能的入口。用 QueryPerformanceFrequency（）和QueryPerformanceCounte（）函数计时，精度比用 clock（）高，避免了很多时候因排序速度太快而出现运行时间为 0 的现象。用 srand 函数作为随机数发生

4、器的初始化函数，用rand 产生随机数。把计算得的排序时间存入数组并经冒泡排序得出最快的两种排序法。下面是所用排序法的算法思想：（1）直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录 ai(2#include #include #include #include #define N 30000void Wrong() printf(“n=按键错误!n“);getchar();void Disp(int a)int i;system(“cls“);for(i=0;i0j-) aj=aj-1; aj=temp; void Sel

5、ectSort(int a,int p) /选择排序 int i,j,k; for(i=0;ii;j-) /*比较,找出本趟最小关键字的记录*/if (aj=0;i-)creatheap(a,i,n-1);for(i=n-1;i=1;i-)t=a0;a0=ai;ai=t;creatheap(a,0,i-1);void quicksort(int a,int n,int p) int i,j,low,high,temp,top=-1;struct nodeint low,high;stN;top+;sttop.low=0;sttop.high=n-1;while(top-1) low=sttop

6、.low;high=sttop.high;top-;i=low;j=high;if(lowtemp)j-;if(ij)ai=aj;i+;while(ijif(ij)aj=ai;j-;ai=temp;top+;sttop.low=low;sttop.high=i-1;top+;sttop.low=i+1;sttop.high=high;double TInsertSort(int a,int p)int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency( LARGE_INTEGE

7、R m_liPerfStart=0;QueryPerformanceCounter(InsertSort(b,p);LARGE_INTEGER liPerfNow=0;QueryPerformanceCounter(double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;if(p!=6)Disp(b);getchar();printf(“n 用直接插入排序法用的时间为%f 秒；“,time);FILE *fp;fp=fopen(“直接插入排序.txt“,“w“);for(i=0;iN

8、;i+)fprintf(fp,“%d “,bi);fclose(fp);return(time);double TSelectSort(int a,int p)int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency( LARGE_INTEGER m_liPerfStart=0;QueryPerformanceCounter(SelectSort(b,p);if(p!=6)Disp(b);getchar();LARGE_INTEGER liPerfNow=0;QueryPerf

9、ormanceCounter(double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;printf(“n 用直接选择排序法用的时间为%f 秒；“,time);FILE *fp;fp=fopen(“直接选择排序.txt“,“w“);for(i=0;iN;i+)fprintf(fp,“%d “,bi);fclose(fp);return(time);double TBubbleSort(int a,int p)int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_

10、INTEGER m_liPerfFreq=0;QueryPerformanceFrequency( LARGE_INTEGER m_liPerfStart=0;QueryPerformanceCounter(BubbleSort(b,p);LARGE_INTEGER liPerfNow=0;QueryPerformanceCounter(double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;if(p!=6)Disp(b);getchar();printf(“n 用冒泡排序法用的时间

11、为%f 秒；“,time);FILE *fp;fp=fopen(“冒泡排序.txt“,“w“);for(i=0;iN;i+)fprintf(fp,“%d “,bi);fclose(fp);return(time);double Theapsort(int a,int n,int p) int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency( LARGE_INTEGER m_liPerfStart=0;QueryPerformanceCounter(heapsort(b,N,p

12、);LARGE_INTEGER liPerfNow=0;QueryPerformanceCounter(double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;if(p!=6)Disp(b);getchar();printf(“n 用堆排序法用的时间为%f 秒；“,time);FILE *fp;fp=fopen(“堆排序.txt“,“w“);for(i=0;iN;i+)fprintf(fp,“%d “,bi);fclose(fp);return(time);double Tquick

13、sort(int a,int n,int p)int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency( LARGE_INTEGER m_liPerfStart=0;QueryPerformanceCounter(quicksort(b,N,p);LARGE_INTEGER liPerfNow=0;QueryPerformanceCounter(double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;if(p!=6)Disp(b);getchar(); printf(“n 用快速排序法用的时间为%f 秒；“,time);FILE *fp;fp=fopen(“快速排序.txt“,“w“); for(i=0;iN;i+)fprintf(fp,“%d “,bi);fclose(fp); return(time);