软件算法综合设计报告书-排序

软件算法综合设计说明书软件算法综合设计说明书排序综合学院：信息与电气工程学院专业：计算机科学与技术班级：10-02姓名：学号：1002102142012.6.28软件算法综合设计说明书一、课程设计目的1、初步具备根据应用需求选择合理数据结构并进行算法设计的能力；2、进一步提升C语言的应用能力；3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；6、提升文档写作能力二、课程设计题目及要求排序综合（限3人完成）利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。三、题目分析冒泡排序：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。四、大体设计五、设计详细源代码1.冒泡排序#include<iostream>#include<time.h>usingnamespacestd;#defineN20000voidmain(){ inta[N]; inti,j,temp; srand(time(0)); for(i=0;i<N;i++) { a[i]=rand(); } intflag=1; for(i=0;i<N-1&&flag==1;i++) { flag=0; for(j=0;j<N-i-1;j++) { if(a[j+1]<a[j]) { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; flag=1; } } } for(i=0;i<N;i++) { printf("%d",a[i]); }}2、统计性能#include<stdio.h>#include<stdlib.h>#include<time.h>#defineN10000voidmain(){inti,j,k,n;intn1,t;inta[N],b[N];FILE*fp;clock_tstart,finish;inttime1,time2,time3;printf("输入要产生的随机数个数:");scanf("%d",&n);srand((unsigned)time(NULL));for(i=0;i<n;i++)a[i]=rand();for(i=0;i<n;i++)b[i]=a[i];printf("**************************\n");printf("\t插入排序\n");printf("**************************\n");start=clock();for(i=1;i<n;i++){t=b[i];for(j=i-1;j>=0&&t<b[j];j--)b[j+1]=b[j];b[j+1]=t;}finish=clock();time1=finish-start;printf("插入排序耗时%d毫秒!\n\n\n",time1);fp=fopen("output1.txt","w");for(i=0;i<n;i++)fprintf(fp,"%d",b[i]);fclose(fp);for(i=0;i<n;i++)b[i]=a[i];printf("**************************\n");printf("\t选择排序\n");printf("**************************\n");start=clock();for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(b[k]>b[j])k=j;t=b[i];b[i]=b[k];b[k]=t;}finish=clock();time2=finish-start;printf("选择排序耗时%d毫秒!\n\n\n",time2);fp=fopen("output2.txt","w");for(i=0;i<n;i++)fprintf(fp,"%d",b[i]);fclose(fp);for(i=0;i<n;i++)b[i]=a[i];printf("**************************\n");printf("\t冒泡排序\n");printf("**************************\n");start=clock();n1=n-1;while(n1>0){j=0;for(i=0;i<n1;i++)if(b[i]>b[i+1]){t=b[i];b[i]=b[i+1];b[i+1]=t;j=i;}n1=j;}finish=clock();time3=finish-start;printf("冒泡排序耗时%d毫秒!\n\n\n",time3);fp=fopen("output3.txt","w");for(i=0;i<n;i++)fprintf(fp,"%d",b[i]);fclose(fp);}六、程序的调试与运行结果说明运行结果1、使用冒泡程序完成题目要求运行结果如图1：图1运行结果2、三钟排序方法耗时结果如图2：图2结果说明：插入排序和选择排序耗费时间较少七、课程设计总结通过这次课程设计的学习让我学会了许多，加深了对数据结构排序算法的认识。在这次课程设计中，我们完成了每种排序算法。排序算法选了三个，包括：插入排序、选择排序、冒泡排序。同时也实现了随机数的生成。并把排序后的结果保存在不同的文件中。虽然在算法完成的过程中从网上参考了一些资料，但对这次课程设计的成果还是非常满意的。这次的课程设计还有很多不足之处，如链表存储结构中的堆排序算法，当排序个数过多时，就会等待很长时间。可能时调用的函数过多的原因造成的，但排序是正确的。用指针代替函数的调用。还有就是随机数不能随时更改，只能设定一次。链表归并算法不是对链表直接操作，而是将链表中的元素放入数组中进行排序，我想了很多方法都没有想出对链表的直接操作的算法。由于时间限制，只在课程设计快结束时完成了产生随机文件这部分，我想以后有时间再来完成它。同时在完成这个课程设计后，我也学到了很多知识，并能训练的掌握他们了。首先学会了随机数的产生。熟练的撑握了C语言的文件读写操作。撑握了每种排序算法的基本思想，并从同学那里学会了编写程序的一般步骤：思考问题，写出解决方案