MFC排序综合实验报告.doc

青岛理工大学数据结构课程设计报告题目： 排序综合 院（系）：计算机工程学院 学生姓名: 班级： 学号:起迄日期: 指导教师: 20112012年度 第 2 学期 一、需求分析 1. 问题描述：（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 2.基本功能（1）显示随机数：调用Dip()函数输出数组a。数组a中保存有随机产生的随机数。 （2）直接选择排序：通过n-I次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之。 （3）冒泡排序：如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较。 （4）快速排序：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 （5）直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。设整个排序有n个数，则进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序列为止。（6） 希尔排序：将随机数组进行希尔排序，希尔增量dltak=2(15-k)-1.（7） 堆排序：不断对对进行筛选和构建大堆顶，并进行值得交换排序。（7）显示各排序算法排序后的的数据和时间效率，并比较找出其中2种较快的方法。 3.输入输出 输入是按按钮输入，分别有插入，选择，快速，冒泡，堆，希尔，效率，显示，退出按钮。 输出有两个编辑框，分别显示随机数和排序时间，并能显示较快两种排序方式的时间。二、 概要设计1. 设计思路：用MFC设置界面，用各种按钮显示各种功能。使用随机种子，随机函数来产生数字并存入数组中。分别使用直接插入排序，选择排序，快速排序，冒泡，堆，希尔排序等方法进行排序，并调用高精度计数来对时间进行计算，选出较快两种方式。 2.数据结构设计：ADT orderadlelist数据对象：D=ai|ai属于整型数据关系：R1=|ai-1,ai属于D基本操作：Bubblesort(int a) 操作结果：对数组a进行冒泡排序，返回值为空。Heapsort(int a,int n)操作结果：对数组a进行堆排序，返回值为空。InsertSort(int a,int n)操作结果：对数组a进行插入排序，返回值为空。Quicksort(int a,int n)操作结果：对数组a进行快速排序，返回值为空。Selectsort(int a)操作结果：对数组a进行选择排序，返回值为空。shellInsert(int a,int dk)操作结果：对数组a进行希尔排序，返回值为空。Disp（int a)操作结果：显示数据。TBubblesort(int a) 操作结果：返回冒泡排序所用的时间。Theapsort(int a,int n)操作结果：返回堆排序所用时间。TInsertSort(int a,int n)操作结果：返回插入排序所用时间。TQuicksort(int a,int n)操作结果：返回快速排序所用时间。TSelectsort(int a)操作结果：返回选择排序所用时间。TshellInsert(int a,int dk)操作结果：返回希尔排序所用时间。ADT Orderadlelist 数据存储方式为线性数组的形式。定义方式：int aN 其中N=30000 数组大小为30000.既能满足要求且方便使用。3. 软件结构设计： 功能模块有：直接插入排序，选择排序，快速排序，冒泡排序，堆排序，希尔排序，效率比较，显示随机数，退出操作九个模块。各模块之间是独立的，都是按钮操作触发。插入排序函数：在double TInsertSort(int a)内调用void InsertSort(b)函数和Disp(int a)函数。选择排序：先调用double TSelectSort(int a),再调用void SelectSort(int a)和Disp(int a)函数。快速排序：先调用 double Tquicksort(int a,int n),再调用void quicksort(int a,int n)和Disp(int a);冒泡排序：先调用double TBubbleSort(int a)，在调用void BubbleSort(int a)和Disp(int a)函数。堆排序：先调用double Theapsort(int a,int n)，在调用void heapsort(int a,int n)接着调用void creatheap(int a,int i,int n) 和Disp(int a)函数。希尔排序：先调用double TShellSort(int a,int data)，接着是void SelectSort(int a)和void ShellInsert(int a,int dk) 以及Disp(int a)函数。效率：直接调用以上六个模块，并调用时间排序函数void BubleSort(double a)。显示：调用Disp(int a)函数。退出：调用MessageBox(谢谢使用!); exit(0); 开始 开始界面 按钮堆排序退出显示随机数效率比较希尔排序冒泡排序快速排序选择排序插入排序退出显示随机数显示六种排序时间并显示较快的两种显示随机数和排序时间结束三、 详细设计 1. 程序中的数据结构：int aN; 存储随机数int dlta16; 希尔排序增量存储 struct node 快速排序中用来记录子序列的前后位置 int low,high;stN;2 主函数和其他函数的伪码算法；void CSortDlg:Disp(int a)m_jieguo=;CString s;int i; for(i=1;iN;i+) s.Format(%d,ai);m_jieguo+=s;m_jieguo+= ; if(i)%10=0) m_jieguo+=rn; UpdateData(false);void CSortDlg:ShellInsert(int a,int dk) int i,j,temp;for(i=dk+1;i0&ajtemp;j-=dk)aj+dk=aj;shift+=1;count+;aj+dk=temp;shift+;void CSortDlg:ShellSort(int a,int dlta)int k=0;for(k=0;k=15;k+)ShellInsert(a,dltak);void CSortDlg:InsertSort(int a) int i,j,temp; for(i=1;i0&aj-1temp;j-) aj=aj-1; count+;shift+=1; aj=temp; shift+; void CSortDlg:SelectSort(int a) int i,j,k; for(i=0;iN-1;i+) k=i; for(j=i+1;jN;j+) if(ajak) k=j;count+; if(k!=i) int temp; temp=ak; ak=ai; ai=temp; shift+=3; void CSortDlg:BubbleSort(int a) int i,j,temp; for (i=0;ii;j-) count+; if (ajaj-1) temp=aj; aj=aj-1; aj-1=temp; shift+=3; void CSortDlg:creatheap(int a,int i,int n) int j;int t;t=ai;j=2*(i+1)-1;while(j=n)count+;if(jn)&(ajaj+1)j+;if(t=0;i-)creatheap(a,i,n-1);for(i=n-1;i=1;i-)t=a0;a0=ai;ai=t;shift+=3;creatheap(a,0,i-1);void CSortDlg:quicksort(int a,int n) int i,j,low,high,temp,top=-1; struct node int low,high; stN; top+; sttop.low=0;sttop.high=n-1; while(top-1) low=sttop.low;high=sttop.high; top-; i=low;j=high; if(lowhigh) temp=alow;shift+; while(i!=j) while(count+,itemp)j-; if(ij)ai=aj;i+;shift+; while(count+,ij&aitemp)i+; if(ij)aj=ai;j-;shift+; ai=temp; shift+; top+;sttop.low=low;sttop.high=i-1; top+;sttop.low=i+1;sttop.high=high; double CSortDlg:TShellSort(int a,int data)if(!bt)m_shijian=;CString str;int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); /获取时钟频率LARGE_INTEGER LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart); / 用于得到高精度计时器的值 ShellSort(b,data);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(!bt)Disp(b);m_shijian+=用希尔排序用时为:;str.Format(%f,time);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字比较次数：;str.Format(%d,count);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字移动次数：;str.Format(%d,shift);m_shijian+=str;m_shijian+=rn;UpdateData(false);count=0;shift=0;FILE *fp; fp=fopen(希尔排序.txt,w); for(i=0;iN;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double CSortDlg:TInsertSort(int a)if(!bt)m_shijian=;CString str;int i;int bN; for(i=0;iN;i+) bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart);InsertSort(b);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(!bt)Disp(b);m_shijian+=用插入排序用时为:;str.Format(%f,time);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字比较次数：;str.Format(%d,count);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字移动次数：;str.Format(%d,shift);m_shijian+=str;m_shijian+=rn;UpdateData(false);count=0;shift=0;FILE *fp; fp=fopen(插入排序.txt,w); for(i=0;iN;i+) fprintf(fp,%d ,bi); fclose(fp);return(time);double CSortDlg:TSelectSort(int a)if(!bt)m_shijian=;CString str;int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart);SelectSort(b);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(!bt)Disp(b);m_shijian+=用选择排序用时为:;str.Format(%f,time);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字比较次数：;str.Format(%d,count);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字移动次数：;str.Format(%d,shift);m_shijian+=str;m_shijian+=rn;UpdateData(false);count=0;shift=0;FILE *fp; fp=fopen(选择排序.txt,w);for(i=0;iN;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double CSortDlg:TBubbleSort(int a)if(!bt)m_shijian=;CString str;int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); /获取时钟频率LARGE_INTEGER LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart); / 用于得到高精度计时器的值BubbleSort(b);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(!bt)Disp(b);m_shijian+=用冒泡排序用时为:;str.Format(%f,time);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字比较次数：;str.Format(%d,count);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字移动次数：;str.Format(%d,shift);m_shijian+=str;m_shijian+=rn;UpdateData(false);count=0;shift=0;FILE *fp; fp=fopen(冒泡排序.txt,w); for(i=0;iN;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double CSortDlg:Theapsort(int a,int n) if(!bt)m_shijian=;CString str;int i;int bN;for(i=0;iN;i+)bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart);heapsort(b,N);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(!bt)Disp(b);m_shijian+=用堆排序用时为:;str.Format(%f,time);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字比较次数：;str.Format(%d,count);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字移动次数：;str.Format(%d,shift);m_shijian+=str;m_shijian+=rn;UpdateData(false);count=0;shift=0;FILE *fp; fp=fopen(堆排序.txt,w);for(i=0;iN;i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double CSortDlg:Tquicksort(int a,int n)if(!bt)m_shijian=;CString str;int i;int bN; for(i=0;iN;i+) bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart);quicksort(b,N);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(!bt)Disp(b);m_shijian+=用快速排序用时为:;str.Format(%f,time);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字比较次数：;str.Format(%d,count);m_shijian+=str;m_shijian+=rn;m_shijian+=关键字移动次数：;str.Format(%d,shift);m_shijian+=str;m_shijian+=rn;UpdateData(false);count=0;shift=0;FILE *fp;fp=fopen(快速排序.txt,w); for(i=0;iN;i+) fprintf(fp,%d ,bi); fclose(fp); return(time);void CSortDlg:BubleSort(double a) int i,j; double temp; for(i=1;i=i;j-) if(aj+1aj) temp=aj+1; aj+1=aj; aj=temp; 3. 画出函数之间的调用关系图.选择排序按钮插入按钮 double TInsertSort(int a)double TSelectSort(int a)Disp(int a)void InsertSort(b)void SelectSort(int a) Disp(int a)冒泡按钮快速按钮double TBubbleSort(int a)double Tquicksort(int a,int n)Void Disp(int a)Void BubbleSort(int a)quicksort(int a,int n)Void Disp(int a)希尔按钮 堆按钮DoubleTShellSort(int a,int data)Double Theapsort(int a,int n)Void Disp(int a)void ShellSort(int a,int dlta)Void Disp(int a)Void heapsort(int a,int n)void ShellInsert(int a,int dk)void creatheap(int a,int i,int n)退出按钮显示按钮Exit(0)Void Disp(int a)四、 调试分析 1.实际完成的情况说明.实际完成了插入，选择，快速，冒泡，堆，希尔排序，同时又对六种排序方式时间的比较，并能显示随机数，在使用完后还能退出。2. 程序的性能分析，包括时空分析。程序容错等其他方面都很强，因为是按钮操作，并不会有按错处理。3. 上机过程中出现的问题及其解决方案。出现的问题，主要体现在希尔排序时，第一个元素并未排序，通过调节希尔排序的增量变化来处理。4. 程序中可以改进的地方说明。尚待改进的地方主要在界面