数据结构课程设计多种排序.doc

课 程 设 计 说 明 书课程名称： 数据结构课程设计 设计题目： 多种排序 院 系： 计算机科学与信息工程学院 学生姓名： 学 号： 专业班级： 13级网络工程 指导教师： 2015年 6 月 23日课 程 设 计 任 务 书设计题目 多种排序学生姓名所在院系计科院专业、年级、班13级网络工程设计要求：利用随机函数产生N个随机整数（10000以上），对这些数进行多种方法进行排序学生应完成的工作： 1) 我采用插入排序、希尔排序两种算法完成多种排序。2) 统计插入排序，希尔排序两种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出这两种方法实现较快的方法。并将数据序列和不同的查找算法的性能结果记录入txt文件。参考文献阅读：1) 清华大学出版社数据结构 编著：严蔚敏 吴伟民 2) 清华大学出版社C程序设计教程 编著：谭浩强 工作计划：1) 两天时间讨论框架，由组长分配任务。2) 三人合作每人解决两种排序方法由组长组合起来。任务下达日期： 2015年 6月 15 日 任务完成日期： 2001年 6月 23日指导教师（签名）：冯贺 学生（签名）： 张浩多种排序摘 要：本次课程设计所要求的排序方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序，基本上将我们学习过的排序方法都囊括在内，可以说这次课程设计是对我们学过的排序算法的一个总结和对比。通过实验中各种排序方法所用的时间对比，可以让我们对每种排序方法的性能有一个清晰的认识，有利于我们以后在做某些程序时更好的选择最好的排序方法。关键词：(1)六种排序 插入排序 希尔排序 起泡排序 快速排序选择排序 堆排序 (2) 排序方法的性能关键问题:核心问题: 排列组合数据模型（逻辑结构）：30000个随机数存储结构: 保存在不同的文件核心算法: 直接插入、直接选择、冒泡、快速排序、堆排序的算法输入数据: 初始化数组：rand()%50000+1 输出数据：排序内容到文件，排序所用时间目 录1. 设计背景51.1 总设计52.设计方案52.1设计思想52.2主要思想和流程图63方案实施73.1程序的实现73.2主要源代码及说明74结果与结论204.1运行主界面204.2各种排序方法运行结果204.3 运行结论245收获与致谢246参考文献247 附件 241. 设计背景1.1总设计分别实现直接插入排序、希尔排序、直接选择排序、冒泡排序、快速排序、堆排序的算法。从时间的角度来分析各种排序的性能。通过测试多组数据来掌握各种排序的方法及适用场合，并能在解决实际问题灵活运用。在编写代码的时候，有以下几个问题：（1）建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环使用系统。（2）分别实现直接插入排序、希尔排序、直接选择排序、冒泡排序、快速排序、堆排序的算法。（3）通过冒泡排序法来测试每组数据用那种排序算法最优。2.设计方案2.1 设计思想建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环使用系统。分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。（1） 直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录ai(2=i=n)插入到有序子序列a1.i-1中，使记录的有序序列从a1.i-1变为a1.i ，最终使整个文件有序。共进行n-1趟插入。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。（2） 希尔排序的基本思想是基于分组，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入排序为止。 （3）直接选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1=in)趟简单选择排序是，从无序序列ai.n的n-i+1记录中选出关键字最小的记录，和第i个记录交换，使有序序列逐步扩大，最后整个文件有序。共进行n-1趟选择。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是不稳定排序。(4)冒泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。(5)快速排序思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。(6)堆排序基本思想是：堆是n个元素的序列，先建堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n-1记录重新调整为堆（调堆的过程称为“筛选”），再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供交换用的辅助空间，调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较。2.2 主要算法和流程图输入序号退出显示随机数时间效率比较堆排序快速排序冒泡排序直接选择排序希尔排序直接插入排序结束显示各个排序法对同一组数据排序所用的时间和其中较快的两种方法显示排序后的数据和时间效率 开始 1 2 3 4 5 6 7 8 0 3. 方案实施3.1 程序的实现程序实现时应考虑的问题void InsertSort(int a,int p)void shellSort(int a,int p)void SelectSort(int a,int p)void heapsort(int a,int n,int p)void quicksort(int a,int n, int p)void BubbleSort(int a,int p)void Disp(int a)void creatheap(int a,int i ,i,nt n) double Tquicksort(int a,int left, int right,int p)double TShellSort(int a,int p)double TBubbleSort(int a,int p)void BubleSort(double a)时间数组的冒泡排序double TInsertSort(int a,int p)double Theapsort(int a,int n,int p)double TSelectSort(int a,int p)3.2 主要源代码及说明#include stdio.h#include conio.h #include stdlib.h#include windows.h#include time.h#define N 10000void Wrong() printf(n=按键错误!n);getchar();void Disp(int a)int i;system(cls); for(i=0;iN;i+) if(i-1)%10=9) printf(n); printf(%-7d,ai); void InsertSort(int a,int p) /插入排序 int i,j,temp; for(i=1;iN;i+) temp=ai; for(j=i;j0aj-1temp;j-) aj=aj-1; aj=temp; void shellSort(int a,int p) /希尔排序 int i,j,temp; for(i=p;iN;i+) if(aiai-p) temp=ai; for(j=i-p;j=0(tempaj);j=j-p) aj+p=aj; aj+p=temp; void SelectSort(int a,int p) /选择排序 int i,j,k; for(i=0;iN-1;i+) k=i; for(j=i+1;jN;j+) if(ajak) k=j; if(k!=i) int temp; temp=ak; ak=ai; ai=temp; void BubbleSort(int a,int p) /*冒泡排序算法*/int i,j,temp;for (i=0;iN-1;i+) for (j=N-1;ji;j-) /*比较,找出本趟最小关键字的记录*/ if (ajaj-1) temp=aj; /*进行交换,将最小关键字记录前移*/ aj=aj-1; aj-1=temp; void creatheap(int a,int i,int n) /创建堆int j;int t;t=ai;j=2*(i+1)-1;while(j=n)if(jn)(ajaj+1)j+;if(taj)ai=aj;i=j;j=2*(i+1)-1;elsej=n+1;ai=t;void heapsort(int a,int n,int p) /堆排序int i;int t;for(i=n/2-1;i=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 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; while(i!=j) while(ijajtemp)j-; if(ij)ai=aj;i+; while(ijaitemp)i+; if(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(m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(m_liPerfStart);InsertSort(b,p);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(p!=7)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 TShellSort(int a,int p)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,p);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(p!=7)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 TSelectSort(int a,int p)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,p);if(p!=7)Disp(b);getchar();LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(liPerfNow); 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_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(m_liPerfStart);BubbleSort(b,p);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(p!=7)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 Theapsort(int a,int n,int p) 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,p);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(p!=7)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 Tquicksort(int a,int n,int p)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,p);LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(p!=7) 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);void BubleSort(double a) /时间数组的冒泡排序 int i,j; double temp; for(i=1;i7;i+) for(j=5;j=i;j-) if(aj+1aj) temp=aj+1; aj+1=aj; aj=temp; void menu()printf( * 欢迎来到排序系统! *n); printf( * (1)-直接插入排序 *n);printf( * (2)-希尔排序 *n);printf( * (3)-直接选择排序 *n);printf( * (4)-冒泡排序 *n);printf( * (5)-快速排序 *n);printf( * (6)-堆排序 *n);printf( * (7)-时间效率比较 *n);printf( * (8)-显示随机数 *n);printf( * (0)-退出 *n);printf( *n);printf(n=请在上述序号中选择一个并输入:);void main() int i,p,aN; srand(int)time(NULL); /*随机种子*/ for(i=0;iN;i+) ai=rand()%50000+1; while(1) system(cls); menu(); scanf(%d,p); if(p=0) printf(=谢谢使用!n); getchar(); break; double TIMES6,TIMES16;/时间数组 switch(p) case 1:TInsertSort(a,p);printf(n请按任意键继续.);getchar();break; case 2:TShellSort(a,p);printf(n请按任意键继续.);getchar();break; case 3:TSelectSort(a,p);printf(n请按任意键继续.);getchar();break; case 4:TBubbleSort(a,p);printf(n请按任意键继续.);getchar();break; case 5:Tquicksort(a,N,p);printf(n请按任意键继续.);getchar();break; case 6:Theapsort(a,N,p);printf(n请按任意键继续.);getchar();break; case 7:system(cls);TIMES11=TIMES1=TInsertSort(a,p);TIMES12=TIMES2=TShellSort(a,p);TIMES13=TIMES3=TSelectSort(a,p);TIMES14=TIMES4=TBubbleSort(a,p);TIMES15=TIMES5=Tquicksort(a,N,p);TIMES16=TIMES6=Theapsort(a,N,p);getchar(); BubleSort(TIMES); printf(nn); printf(排序这组数据两种较快的排序法分别是：n); if(TIMES1=TIMES11) printf(直接插入排序:%f秒!n,TIMES1); if(TIMES1=TIMES12) printf(希尔排序:%f秒!n,TIMES1); if(TIMES1=TIMES13) printf(直接选择排序:%f秒!n,TIMES1); if(TIMES1=TIMES14) printf(冒泡排序:%f秒!n,TIMES1); if(TIMES1=TIMES15) printf(快速排序:%f秒!n,TIMES1); if(TIMES1=TIMES16) printf(堆排序:%f秒!n,TIMES1); if(TIMES1!=TIMES2) if(TIMES2=TIMES11) printf(直接插入排序:%f秒!n,TIMES2); if(TIMES2=TIMES12) printf(希尔排序%f秒!n,TIMES2); if(TIMES2=TIMES13) printf(直接选择排序%f秒!n,TIMES2); if(TIMES2=TIMES14) printf(冒泡排序%f秒!n,TIMES2); if(TIMES2=TIMES15) printf(快速排序%f秒!n,TIMES2); if(TIMES2=TIMES16) printf(堆排序%f秒!n,TIMES2); printf(n请按任意键继续.);srand(int)time(NULL); for(i=0;iN;i+) ai=rand()%1