西北工业大学程序设计大作业

...wd......wd......wd...学院××××学院班级××××××××学号××××××××姓名×××目录TOC\o"1-4"\h\z1摘要31.1设计题目31.2设计内容31.3开发工具31.4应用平台32详细设计32.1程序构造32.2主要功能42.3函数实现52.4开发日志73程序调试及运行73.1程序运行结果73.2程序使用说明123.3程序开发总结124附件〔源程序〕121摘要1.1设计题目算法型大作业题目：编写七种排序算法的演示程序。1.2设计内容编写快速排序、插入排序、选择排序、冒泡排序、堆排序、归并排序、基数排序函数，通过主函数调用以实现七种排序算法的演示。1.3开发工具VisualC++6.01.4应用平台Windows2000/XP/Vista32位2详细设计2.1程序构造程序的整体构造与流程见以下列图所示。程序运行时在主菜单中输入序号选择排序方法或选择完毕程序，当进展某种排序方法后，在主函数中输入待排数据个数和待排数据，通过调用对应的排序函数实现排序并输出。该排序完毕后再次进入主函数，通过循环重复上述操作。其中，主函数中将数组地址和待排序数据个数传递给排序函数，在排序函数中实现排序功能。输出排序结果开场快速插入选择冒泡堆排归并基数选择排序方法进入主菜单输出排序结果开场快速插入选择冒泡堆排归并基数选择排序方法进入主菜单退出系统退出系统2.2主要功能函数的功能为对快速排序、插入排序、选择排序、冒泡排序、堆排序、归并排序、基数排序算法的演示。主函数：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者退出。快速排序函数：根据快速排序的算法，最后输出插入排序函数：根据插入排序的算法，最后输出选择排序函数：根据选择排序的算法，最后输出冒泡排序函数：根据冒泡排序的算法，最后输出堆排序函数：根据堆排序的算法，最后输出归并排序函数：根据归并排序的算法，最后输出基数排序函数：根据基数排序的算法，最后输出2.3函数实现主函数:在主函数中对菜单输出，通过switch语句中的case分支选择所需要的排序方法；通过while循环使演示程序在运行时能够持续进展快速排序：快速排序〔kuaisu〕又被称做分区交换排序，这是一种平均性能非常好的排序方法。其算法根本思想是：任取排序表中的某个数据元素(例如取第一个数据元素)作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表：左侧子表中所有数据元素的关键字都小于基准数据元素的关键字。右侧子表中所有数据元素的关键字都大于或等于基准数据元素的关键字，基准数据元素则排在这两个子表中间(这也是该数据元素最终应安放的位置)，然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1，则排序完毕。插入排序：插入排序〔charu〕的根本思想：开场时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开场依次把数据元素按关键字大小插入到已排序的局部排序表的适当位置。当插入第i(1<i<=n)个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进展比拟，找到插入位置后就将第i个数据元素插入。如此进展n-1次插入，就完成了排序。以下是在顺序表上实现的直接插入排序在顺序表上进展直接插入排序时，当插入第i(1<i<=n)个数据元素时，前面的A[0]、A[1]、…、A[i-2]已经排好序，这时，用A[i-1]的关键字依次与A[i-2],A[i-3],…的关键字顺序进展比拟，如果这些数据元素的关键字大于A[i-1]的关键字，则将数据元素向后移一个位置，当找到插入位置后就将A[i-1]插入，就完成了A[0],A[1],…,A[n-1]的排序。选择排序选择排序〔xuanze〕的算法根本思想是：a)开场时设i的初始值为0。b)如果i<n-1，在数据元素序列A[i](A[n-1]中，选出具有最小关键字的数据元素A[k]；否则算法完毕。c)假设A[k]不是这组数据元素中的第一个数据元素〔i≠k〕，则将A[k]与A[i]这两数据元素的位置对调；d)令i=i+1转步骤b)。冒泡排序：冒泡排序(maopao)的根本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字A[0]和A[1]进展比拟。如果前者大于后者，则进展交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡，它将关键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位置移动。然后进展第二趟排序，对排序表中前n-1个元素进展与上述同样的操作，其结果使整个排序表中关键字次大的数据元素被移到A[n-2]的位置。如此最多做n-1趟冒泡就能把所有数据元素排好序。堆排序：堆排序(duipai)sa.对排序表中的数据元素，利用堆的调整算法形成初始堆。b.输出堆顶元素。c.对剩余元素重新调整形成堆。d.重复执行第b、c步，直到所有数据元素被输出。如果建设的堆满足最大堆的条件，则堆的第一个数据元素A[0]具有最大的关键字，将A[0]与A[n-1]对调，把具有最大关键字的数据元素交换到最后，再对前面的n-1个数据元素使用堆的调整算法，重新建设最大堆，结果把具有次最大关键字的数据元素又上浮到堆顶，即A[0]的位置，再对调A[0]和A[n-2]，…，如此反复执行n-1次，最后得到全部排序好的数据元素序列。归并排序：其根本思想是：设有两个有序表A和B，其数据元素个数〔表长〕分别为n和m，变量i和j分别是表A和表B的当前检测指针；设表C是归并后的新有序表，变量k是它的当前存放指针。开场时i、j、k都分别指向A、B、C三个表的起始位置；然后根据A[i]与B[j]的关键字的大小，把关键字小的数据元素放到新表C[k]中；且相应的检测指针〔i或j〕和存放指针k增加1.如此循环，当i与j中有一个已经超出表长时，将另一个表中的剩余局部照抄到新表C[k]~C[m+n]中。下面的归并算法中，两个待归并的有序表首尾相接存放在数组sourcetable.arr[]中，其中第一个表的下标范围从left到mid，另一个表的下标范围从mid+1到right。前一个表中有mid-left+1个数据元素，后一个表中有right–mid个数据元素。归并后得到的新有序表有right–mid个数据元素。归并后得到的新有序表存放在另一个辅助数组mergedtable.arr[]中，其下标范围从left到right。一趟归并算法：设数组sourcetable.arr[0]到sourcetable.arr[n-1]中的n个数据元素已经分为一些长度为len的归并项，将这些归并项两两归并，归并成一些长度为2len的归并项，结果放到mergedtable.arr[]中。如果n不是2len的整数倍，则一趟归并到最后，可能遇到两种情况：剩下一个长度为len的归并项和一个长度缺乏len的归并项，可用一次merge算法，将它们归并成一个长度小于2len的归并项。只剩下一个归并项，其长度小于或等于len，可将它直接复制到数组mergedtable.arr[]中。在一趟归并算法的根基上，实现两路归并排序算法。在两路归并排序算法中，初始排序表存放在数组table.arr[]中,第一趟归并将table.arr[]中的归并项两两归并，结果存放在辅助数组temptable.arr[]中。第二趟将temptable.arr[]中的归并项两两归并，结果放回原数组table.arr[]中，如此反复进展。为了将最后归并结果仍放在数组table.arr[]中，归并趟数应为偶数。如果做奇数趟就能完成时，最后还需要执行一次一趟归并过程，由于这时的归并项长度len>=n，因此在则趟归并中while循环不执行，只做把temptable.arr[]中的数据元素复制到table.arr[]的工作。基数排序：“基数排序法〞〔radixsort〕则是属于“分配式排序〞〔distributionsort〕，基数排序法又称“桶子法〞〔bucketsort〕或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶〞中，藉以到达排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比拟性排序法。具体可以参看后面的代码进展理解。其它： 使用了stdlib头文件里包含的系统函数，包括清屏函数和运行时的暂停，增强了程序运行时的效果。2.4开发日志在教师布置了大作业的题目后，我就把题目下载下来并进展分析已选择适宜的题目。经过我的慎重考虑，选择了算法型大作业题目中的编写七种排序算法的演示程序，觉得自己有能力把这道题目很好完成。在认真分析连题目后，根本确定了整体的思路，但是其中有堆排序，归并排序，基数排序我没有在教材中接触过，于是借助了图书馆和网络上的资源，重点对这三的函数进展编写。在编写大作业过程中大的困难我没有遇到，只是有些小的疏忽常常导致程序无法运行，如形参和实参的不一致等。我也在其中意识到对知识掌握的不够熟练，在解决了这些问题后，我觉得自己对程序的编写更加熟练了，对问题的分析也更加严谨了。在C程序设计的实验和理论考试之前代码已根本完成。在考试完毕后，我又对程序稍微进展了修改，使之运行时效果更好。接着开场写实验报告，整理自己的大作业。我对我的作业是很满意的。3程序调试及运行3.1程序运行结果1.进入程序运行后所显示的菜单：2.快速排序：3.插入排序：4.选择排序：5.冒泡排序：6.堆排序：7.归并排序：8.基数排序：9.完毕：3.2程序使用说明1.翻开源程序，调试完毕后开场运行，开场进展七种算法的演示；2.按照说明进展输入,选择数字1~7即可进入相应的排序算法演示程序，选择8完毕程序；3.选择排序的方法后，按要求输入待排数据的个数，然后输入待排序数据即可〔数据排序完毕后，会自动清屏，进入菜单进展接下来的选择〕；4.应当注意，本演示程序对数据进展的是升序；3.3程序开发总结在选择这个题目时，我觉得难度系数10对我有挑战性，并且我对排序有相比照拟熟悉，所以就选了这个题目。但是在编写过程中却遇到很多问题。我和我的同学进展了讨论，查阅了图书馆和网络上的资料，结合力我个人对此题目的理解对各种问题进展了处理，学到了很多教材上没有的知识。从这次实践中，我意识到自己还有很多缺乏之处。能力也得到了提高。我在进展编程时还需要翻书查找，对于这一点，只能说对知识的学习还不够扎实，所以有空时还应该继续熟悉这门课程。另外，就是对于错误的处理，不能得心应手，不能正确处理一些简单的错误。对于逻辑上的错误，不能够立即找到出错点，往往需要向同学请教才能找出错误，并且改正。我觉得这是自己单独思考能力不高的问题，遇事需要自己仔细想想，假设还不能改正，再请教别人也不迟。从总体上说，最终结果我很满意，我觉得我所设计的程序操作方便，功能良好。我在上面花费了很多时间和精力，对作业不断进展修改和完善，我很有成就感。我的能力在这之中得到了提高。4附件〔源程序〕#include<stdio.h>#include<stdlib.h>////////////////////**********快速排序**********//////////////////////voidkuaisu(intA[],intn) { inti,j,k,t,p; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(A[j]<A[k])k=j; t=A[k]; A[k]=A[i]; A[i]=t; printf("第%d趟:",i+1); for(p=0;p<n;p++) { printf("%d",A[p]); } printf("\n"); } printf("\n排序结果:"); for(i=0;i<n;i++) printf("%d",A[i]); printf("\n"); printf("\n"); system("pause"); system("CLS");}////////////////////**********插入排序**********//////////////////////voidcharu(intA[],intn){ inti,k,t,j,h=1; for(i=1;i<n;i++) { t=A[i]; k=i-1; while(t<A[k]) { A[k+1]=A[k]; k--; if(k==-1)break; printf("第%d趟:",h++); for(j=0;j<n;j++) printf("%d",A[j]); printf("\n"); } A[k+1]=t; } printf("\n排序结果:"); for(i=0;i<n;i++) printf("%d",A[i]); printf("\n"); printf("\n"); system("pause"); system("CLS");}////////////////////**********选择排序**********//////////////////////voidxuanze(intA[],intn){ inti,j,k,t,l,h=1; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(A[j]<A[k])k=j; if(i!=k) { t=A[i]; A[i]=A[k]; A[k]=t; printf("第%d趟:",h++); for(l=0;l<n;l++) printf("%d",A[l]); printf("\n"); }; } printf("\n排序结果:"); for(i=0;i<n;i++) printf("%d",A[i]); printf("\n"); printf("\n"); system("pause"); system("CLS");}////////////////////**********冒泡排序**********//////////////////////voidmaopao(intA[],intn){ inti,j,t,h=1,p; for(j=0;j<n-1;j++) for(i=0;i<n-1-j;i++) { if(A[i]>A[i+1]) t=A[i],A[i]=A[i+1],A[i+1]=t,p++; printf("第%d趟:",h++); for(p=0;p<n;p++) printf("%d",A[p]); printf("\n"); } printf("\n排序结果:"); for(i=0;i<n;i++) printf("%d",A[i]); printf("\n"); printf("\n"); system("pause"); system("CLS");}/////////////////////**********堆排序**********///////////////////////voidshift(intA[],inti,intm){ intk,t;t=A[i];k=2*i+1;while(k<m){if((k<m-1)&&(A[k]<A[k+1]))k++;if(t<A[k]){A[i]=A[k];i=k;k=2*i+1;}elsebreak; }A[i]=t;}voidduipai(intA[],intn)//a为排序数组，n为数组大小{ inti,k,h=1,j; for(i=n/2-1;i>=0;i--)shift(A,i,n); for(i=n-1;i>=1;i--) { k=A[0];A[0]=A[i];A[i]=k; shift(A,0,i); printf("第%d趟:",h++); for(j=0;j<n;j++) printf("%d",A[j]); printf("\n"); } printf("\n排序结果:"); for(i=0;i<n;i++) printf("%d",A[i]); printf("\n"); printf("\n"); system("pause"); system("CLS");}////////////////////**********归并排序**********//////////////////////voidmerge(intnumber[],intfirst,intlast,intmid){intnumber_temp[10]={0};inti=first,j=mid+1,k;for(k=0;k<=last-first;k++){if(i==mid+1){number_temp[k]=number[j++];continue;}if(j==last+1){number_temp[k]=number[i++]; continue;}if(number[i]<number[j])number_temp[k]=number[i++];elsenumber_temp[k]=number[j++];}for(i=first,j=0;i<=last;i++,j++)number[i]=number_temp[j];}voidmerge_sort(intnumber[],intfirst,intlast){intmid=0;if(first<last){mid=(first+last)/2;merge_sort(number,first,mid);merge_sort(number,mid+1,last);merge(number,first,last,mid);}}voidguibing(inta[],intn) { inti; merge_sort(a,0,n-1); printf("\n排序结果:"); for(i=0;i<n;i++)printf("%d",a[i]); printf("\n"); printf("\n"); system("pause"); system("CLS");} ////////////////////**********基数排序**********//////////////////////voidjishu(intdata[],intn){inttemp[10][10]={0};intorder[10]={0};inti,j,k,q,lsd;k=0;q=1;while(q<=n) {for(i=0;i<n;i++) {lsd=((data[i]/q)%n);temp[lsd][order[lsd]]=data[i];order[lsd]++;}for(i=0;i<n;i++) {if(order[i]!=0)for(j=0;j<order[i];j++) {data[k]=temp[i][j];k++;}order[i]=0; }q*=n;k=0; } printf("\n排序结果:"); for(i=0;i<n;i++) printf("%d",data[i]); printf("\n"); printf("\n"); system("pause"); system("CLS");}////////////////////***********主函数***********//////////////////////intmain(){ intA[100],p,n,i; while(1) { printf("\n\t****************七种排序算法的演示程序***************\n"); printf("\t**\n"); printf("\t*1快速排序