visual_c++_6.0_各种排序的算法_报告及源程序.doc

摘要近几年来，C语言发展迅速，而且成为最受欢迎的语言之一，主要原因是它具有强大的功效，很多著名的系统软件就是由C语言编写出来的。它与汇编语言的结合，更体现出C语言的优越性。排序算法主要有直接插入排序，折半插入排序，希尔排序，冒泡排序，双向冒泡排序，快速排序，选择排序，堆排序，基数排序这几种。通过对各种排序方法的比较，我们能够很直观的发现各种排序方法的特点及各自的优缺点。此次课程设计主要挑选了选择排序、插入排序、冒泡排序这三种排序方法，通过对这三种排序方法的比较，希望能够让大家对一些排序方法有更加直观、深入的了解。设计中主要解决了用time()、srand()函数辅助rand()函数随机产生了0到99999之间的数据；借助指针申请了动态内存解决了将同一随机数组的三次复制进而确保在相同随机数组的基础上三种比较算法的比较；在各种算法中运用clock()函数计算完成比较所用的时间，并在各种比较算法的编程理解中完成比较、交换次数的计数；将随机数组写入文件等问题。关键词：随机数 排序 交换 时间 目录1. 设计内容、设计参数及要求11.1 设计内容11.2 设计参数11.3 要求12. 总体设计思路22.1 设计系统的功能22.2 算法思想22.3 系统的总体框架32.4 系统的总体流程图43. 功能模块的具体设计53.1 main( )主函数53.2 SelectSort( )函数73.3 InsertSort( )函数93.4 PopSort( )函数113.5 将随机数写入程序133.6 welcome( )函数144. 模块的调试及测试155. 总结与个人体会175.1 总结175.2 个人体会176. 致谢197. 参考文献20附程序源代码211. 设 计 内 容 和 要 求1.1 设计内容通过随机函数随机生成100000个数字，这些数字都是在0，99999之间。(2)并通过设计的排序算法进行排序。这些排序算法中包括冒泡法、选择法、插入法，也可以适当选择其他算法，但必须是较为典型的排序算法。(3)排序完毕后应给出相应的比较信息，其中包括排序时间，比较次数和交换次数等信息。(4)在程序的主界面显示出最后的比较结论。(5)查看完比较结果后，即可点击回车退出系统1.2 设计参数(1)将排序前生成的100000个随机数存入一个文本文件中，该文件命名为BeforeSort.txt。(2)将排序好的数字分别按照不同的排序方式存入不同的文件中，冒泡法排序后的数字存入PopSort.txt中，选择法排序后的数字存入SelectSort.txt中，插入法排序后的数字存入InsertSort.txt中。1.3 要求 1.3.1 基本要求精确测试上述三种排序方法对同样的数据进行排序所消耗的时间，比较次数以及交换次数，明确各种排序的编写方法，分析各种排序方法在不同情况下的优劣。1.3.2 附加要求（1）程序启动后有较漂亮的封面页。(2 ) 结果以列表形式，较友好的人机界面显示2. 总 体 设 计 思 路2.1 设计系统的功能在“Before.txt”中存储随机数。 在”SelectSort.txt”、”InsertSort.txt”、”PopSort.txt”中存储经过排序后的有序数列。 通过对主界面中三种排序方法所用时间、比较次数、交换次数等信息的观察，了解到各自排序方法的特点及优劣。2.2 算法思路2.1.1 选择排序为了便于理解，设有10个数分别存在数组元素a0a9中。选择排序法是由大到小依次定位a0a9中恰当的值，a9中放的自然是最小的数。如定位a0,先假定a0中当前值是最大数，a0与后面的元素一一比较，如果a4更大，则将a0、a4交换，a0已更新再与后面的a5a9比较，如果a8还要大，则将a0、a8交换，a0又是新数，再与a9比较。一轮比完以后，a0就是最大的数了，本次比武的武状元诞生了，接下来从a1开始，再来一轮a1就是次大的数，然后从a2开始，当比到a8以后，排序就完成了。2.2.2 插入排序每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序，直到待排序数据元素全部插入完为止。即经过i-1遍处后,L1.i-1己排好序。第i遍处理仅将L插入L1.i-1的适当位置p，原来p后的元素一一向右移动一个位置,使得L1.i又是排好序的序列。2.2.3冒泡排序 首先将第一个记录的随机数和第二个记录的随机数进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的随机数。依此类推，直到第N-1和第N个记录的随机数进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序2.3系统的总体框架图登录选择排序插入排序冒泡排序将排序结果放入文件将排序结果放入文件将排序结果放入文件结束主函数退出2.4 系统的总体流程图调用随机数函数，产生10000个随机数打开一个“BeforeSort.txt”文本文档，将这10000个随机数放到文本文档中选择排序，并得出其时间消耗，比较次数，交换次数插入排序，并得出其时间消耗，比较次数，交换次数冒泡排序，并得出其时间消耗，比较次数，交换次数将经过选择排序好的10000个数字存放到“SelectSort.txt”文本文档将经过插入排序好的10000个数字存放到“InsertSort.txt”文本文档将经过排序好的10000个数字存放到“PopSort.txt”文本文档程序结束退出进入登录界面按“Enter”键进入主界面3.功能模块的具体设计3.1 main( ) 主函数 主函数功能比较简单，用srand( (unsigned)time( NULL ) )语句以及for循环语句产生随机数。打开BeforeSort.txt文本文档，将随机数放入该文本文档中。使用动态内存，定义选择、插入、冒泡三种排序方法。在主函数的前面要写必须的头文件，预定义语句。3.1.1随机函数的产生 函数rand()将产生一个在0到RAND_MAX之间的整数，其中RAND_MAX是头文件中定义的一个符号常量，并且至少是32767，即16位二进制数所能表示的最大整数。并可以利用比例缩放（求余运算）产生一系列0到所需数（小于RAND_MAX）之间的数 。但实际操作中最大只能得到0到10000之间的数，所以采用了分别获取0到10000之间的数加上0到10之间的数最终得到0到100000之间的数的方法。但是rand()函数具有重复性，并且这种重复性可用于验证该函数运行正确与否，故要借助srand()、time()对该函数进行随机化。其中，函数time的返回值是以秒为单位的从1970年1月1日午夜开始到现在所经历的时间，time函数的返回值被转换成一个无符号的种子传递给srand()函数以产生随机数表3.1.1 随机数的产生 中间变量Ri = ka= rand()%10000b = a*10c = rand()%10k = b+cR 05465R1723R28421R369R43623i = 0i Na = rand()%10000rand()%10000b = a*10 c = rand()%10rand()%10k = b+cRi = ki +真int i,a,b,c,k,RNrand()%10000 图3.1.1 随机数生成流程图3.1.2 时间函数的产生时间函数的用法，参考如下程序，使用时间函数，需要引入头文件time.h，同时需要使用函数clock()，clock()函数返回近似调用程序运行时间量的值,该值除以CLOCKS_PER_SEC后转换为秒数.返回-1值表示无法取得时间。#include#includevoid main()clock_t start;clock_t end;int t;long i;start=clock(); /得到程序运行时的时间量的值for(i=0;i=10000;i+); /空循环，耗费时间end=clock();t=(end-start)/CLOCKS_PER_SEC; /得到空循环运行的时间printf(%d,t);3.2 SelectSort（）函数 利用for循环语句，对“BeforeSort.txt“中的随机数进行选择排序，并打开“SelectSort.txt”文本文档，将经过选择排序的数放入该文本文档。用clock-start及clock-end语句计算出选择排序所用的时间，用for循环语句得出比较次数和交换次数。用printf将选择排序时间，比较次数以及交换次数这些信息在主界面中输出。，3.2.1 选择排序程序29void SelectSort(int R ,int n) /*选择排序 int i,k,index,temp; double count1=0.0,cpt1=0.0; FILE*fp; clock_t start; clock_t end; double time1; start=clock(); for(k=0;kn-1;k+) index=k; for(i=k+1;in;i+) cpt1+; if(RiRindex) index=i; if(index!=k) count1+; temp=Rindex; Rindex=Rk; Rk=temp; k = 0k n-1int i , k, index , tempdouble count1,cpt1temp=RindexRindex=RkRk=temp真index =kRi Rindexcpt1+ Index! =k i+ index = i真count1+ 真k+i ni =k+1图3.2.1 选择排序流程图3.3 InsertSort（）函数 利用for循环语句，对“BeforeSort.txt“中的随机数进行选择排序，并打开“InsertSort.txt”文本文档，将经过插入排序的数放入该文本文档。用clock-start及clock-end语句计算出插入排序所用的时间，用for循环语句得出比较次数和交换次数。用printf将插入排序时间，比较次数以及交换次数这些信息在主界面中输出。3.3.1 插入排序程序void InsertSort(int R,int n) /*插入排序*/ int i,j,temp; double count2=0,cpt2=0,cpt3=0; FILE*fp; clock_t start; clock_t end; double time2; start=clock(); for(i=1;i=0;j-) cpt2+; if(temp=Rj) break; Rj+1=Rj; Rj+1=temp; if(j+1=i-1) count2+; else count2=count2+0;i = 1i = 0break是真假图3.3.1 插入排序流程图3.4 Popsort（）函数 利用for循环语句，对“BeforeSort.txt“中的随机数进行选择排序，并打开“PoptSort.txt”文本文档，将经过冒泡排序的数放入该文本文档。用clock-start及clock-end语句计算出冒泡排序所用的时间，用for循环语句得出比较次数和交换次数。用printf将冒泡排序时间，比较次数以及交换次数这些信息在主界面中输出。3.4.1 冒泡排序程序void PopSort(int R ,int n) /*冒泡排序*/ int i,j,t; double count3=0.0, cpt4=0.0; FILE*fp; clock_t start; clock_t end; double time3; start=clock(); for(i=1;in;i+) for(j=0;jRj+1) count3+; t=Rj; Rj=Rj+1; Rj+1=t; cpt4+; i = 1i nj = 0j Rj+1t =Rjint i, j, t,double count3,cpt4Rj=Rj+1 Rj+1= t cpt4+ j +count3+ i+ 真真真假图3.4.1 冒泡排序流程图3.5将随机数组写入文件 3.5.1 随机数组写入程序int *p=NULL; FILE*fp;if(fp=fopen(BeforeSort.txt,w) = NULL) printf(error); exit(0);for(i=0;in;i+)fprintf(fp,%d ,Ri); if(fclose(fp)printf(Can not close the file); exit(0); int i, *fp,nrand()%10000fp=fopen(BeforeSort.txt,w)fprintf(fp,%d ,Ri)i +真fclose(fp)假 i ni = 0图3.5.1 文件写入流程图3.6 welcome（）函数 利用system(cls)系统语句，构建敲击”Enter”键进入主界面的框架。3.6.1“欢迎”界面程序void welcome() printf(n); printf(n); printf( n); printf( 各种排序算法比较 n); printf( - n); printf( (c)All Right Reserved wyy n); printf( n); printf( version 2009 n); printf( n); printf( Press Enter to Continue);getchar(); system(cls); 4. 模 块 的 调 试 及 测 试图1为测试欢迎“登陆”界面，当按“Enter”键进入下一界面。 图1 登陆界面图2为测试10000个随机数经过选择排序、插入排序、冒泡排序后的结果界面。通过这个界面，可以清楚得得到三种排序方法各自的排序时间、比较次数以及交换次数。图2三种排序各自的结果5. 总 结 与 个 人 体 会5.1 总结 该“排序算法比较”基本可以运行，但是还是有不少地方设计的不太科学，而且有些在C语言课程设计指导书上的任务要求没有很好得运行出来。同时在这次课程设计中让我们认识到做程序设计这项工作中我门要具备以下素质： 良好的文档是正规研发流程中非常重要的环节，缺乏文档，一个软件系统就缺乏生命力，在未来的查错，升级以及模块的复用时就都会遇到极大的麻烦。 此外编程是一项高精度的工作所以我们要有规范化，标准化的代码编写习惯通过这次编程我们深深的感受到对代码的变量命名，代码内注释格式，甚至嵌套中行缩进的长度和函数间的空行数字都有明确规定，良好的编写习惯，不但有助于代码的移植和纠错，也有助于不同人员之间的协作。我们还要有模块化思维能力，模块化思维就是编程任何一个功能模块或函数的时候，要多想一些，不要局限在完成当前任务的简单思路上，想想看该模块是否可以脱离这个系统存在，是否可以通过简单的修改参数的方式在其他系统和应用环境下直接引用，这样就能极大避免重复性的开发工作。5.2 个人体会 通过本次的C语言课程设计，对C语言 有了更深入的了解，本来对C语言一些函数、循环和结构变量不是很清楚，运用起来常常出错。但是如今通过2周的C语言程序设计，已经可以熟练正确地运用各类函数、循环变量、结构化的程序设计以及指针。 了解到模块在C语言中运用方式及技巧，为编写一些比较复杂的语句及结构奠定了基础。 在编写程序过程中，发现这确实是有一定难度的，必须对整个设计要求有很好得了解，才能在编写中避免错误的产生。而且在编写时一定要仔细认真地对待每个程序块，尤其要搞清楚指针的指向。 由于知识的局限性，对一些错误不能正确的将它改正。通过老师及同学才将错误改正完毕。 经过这次课程设计，我发现自己存在很多不足之处，我将会在以后的学习中把它们改正过来，努力将C语言学得更好。6. 致 谢 首先感谢学校为我们提供了这么好的一个学习、提升能力的机会以及如此好的上机环境。然后感谢这两周内陪我们一路走来的各位指导老师，在这么炎热的天气里为我们做指导。尤其是向毅老师，感谢您对我们的严格要求，并为我们整理了这么完整的C语言课程设计指导书以及课程设计报告要求。同时也感谢同学在编写课程中对我的帮助，为我指出不足，让我的程序更加羽翼丰满。 7参考文献 王旭等编著.C语言实用界面技术.陕西：西北工业大学出版社，1996 何钦铭 颜晖主编.C语言程序设计. 高等教育出版社，2008 颜晖主编.C语言程序设计实验指导.高等教育出版社，2008程序源代码#include #include #include #include void welcome();void time();void SelectSort(int R ,int n);void InsertSort(int R ,int n); void PopSort(int R ,int n); void main( ) /主函数 system(color 2f);welcome(); int i,k,a,b,c,R100000,n;int *p=NULL; FILE*fp; srand( (unsigned)time( NULL ) ); for( i = 0; i 100000;i+ ) a=rand()%10000; b=a*10; c=rand()%10; k=b+c; Ri=k;n=100000;if(fp=fopen(BeforeSort.txt,w) = NULL) printf(error); exit(0);for(i=0;in;i+)fprintf(fp,%d ,Ri); if(fclose(fp)printf(Can not close the file); exit(0);printf(Reslut:nnn);p=(int*)malloc(sizeof(int)*100000); for(i=0;in;i+)pi=Ri; SelectSort(p,n);/选择排序 for(i=0;in;i+)pi=Ri;InsertSort(p,n);/插入排序for(i=0;in;i+)pi=Ri; PopSort(p,n);/冒泡排序getch(); void SelectSort(int R ,int n) /*选择排序*/ int i,k,index,temp; double count1=0.0,cpt1=0.0; FILE*fp; clock_t start; clock_t end; double time1; start=clock(); for(k=0;kn-1;k+) index=k; for(i=k+1;in;i+) cpt1+; if(RiRindex) index=i; if(index!=k) count1+; temp=Rindex; Rindex=Rk; Rk=temp; if(fp=fopen(SelectSort.txt,w) = NULL)printf(error);exit(0);for(i=0;in;i+)fprintf(fp,%d ,Ri); if(fclose(fp)printf(Can not close the file);exit(0); end=clock(); time1=(double)(end-start)/CLOCKS_PER_SEC; printf(=n); printf(SelectSort:n); printf(Select Sort Spend %.2lf secondsn,time1); printf(Select Sort Compare %.0lf timesn,cpt1); printf(Select Sort Swap %.0lf timesn,count1); printf(nn); void InsertSort(int R,int n) /*插入排序*/ int i,j,temp; double count2=0,cpt2=0,cpt3=0; FILE*fp; clock_t start; clock_t end; double time2; start=clock(); for(i=1;i=0;j-) cpt2+; if(temp=Rj) break; Rj+1=Rj; Rj+1=temp; if(j+1=i-1) count2+; else count2=count2+0; if(fp=fopen(InsertSort.txt,w) = NULL)printf(error);exit(0);for(i=0;in;i+)fprintf(fp,%d ,Ri); if(fclose(fp)printf(Can not close the file);exit(0); end=clock(); time2=(double)(end-start)/CLOCKS_PER_SEC; printf(=n); printf(InsertSort：n); printf(