作业名称： 七种排序的算法演示 学 院：班 级：学 号：姓 名：团队组成：Xxx Xxx Xxx Zwc Zwc
程序设计挑战式课程设计报告
请填写以下十项内容，将表格按页对齐（插入空行），勿删除任何部分。 1、问题与背景（描述程序所要解决的问题或应用背景）
我们学习了多种排序方法，但不清楚这么多种排序方法分别适合在什么情况下使用，该演示程序将体现各排序方式之间的区别，以帮助我们更深层次的了解这些排序。 对冒泡排序、选择排序、插入排序、快速排序、堆排序、归并排序、基数排序进行演示，观察这七种排序的速度和排序过程。其中归并排序、基数排序无法查看排序的“每一趟”，只能看到排序结果，可通过查看源代码进行分析其排序的原理。 其他排序可通过查看每一趟的排序结果分析其排序的原理和过程，并比较各种排序方法的优点和缺点。 2、开发工具（列出所使用的开发工具和第3方开发库）
Code::block 3、主要功能（详细说明程序的功能）
对七种排序进行演示，选择所需要的排序输入所需输入的数字数和所需排序的数字，输出每一趟的排序结果（没有每一趟排序结果的直接输出排序结果）。通过对输出每一趟的排序结果或运行时间来分析各种排序的运行方式和排序速度。 其优点在于通过主函数调用多种排序方式，且不必关闭程序可多次选择运行的方式或者选择关闭程序。 - 2 -
程序设计挑战式课程设计报告
4、设计内容（详细描述解决问题的原理和方法、算法、数据结构等）
结构图如图所示： 冒泡 选择 插入 快速 堆排序 归并 基数 选择排序方式 输入数据 进入主菜单 开始 输出结果 退出 程 序 通过在主函数中调用显示函数和各排序函数实现各个排序演示或结束程序。输入排序数字的数量和需排序数字，输出排序结果或者选择退出程序。 - 3 -
程序设计挑战式课程设计报告
5、程序文件与工程名称（标出程序中所有文件名、工程名称及其说明）
源文件： 排序.c 头文件： paixu.h disolay.c 应用程序：排序.exe O文件：排序.o 6、函数模块（程序中各个函数的原型声明及其说明）
主函数: 在主函数中对菜单输出，通过switch语句中的case分支选择所需要的排序方法；通过while循环使演示程序在运行时能够持续进行 快速排序（quicksort）又被称做分区交换排序，这是一种平均性能非常好的排序方法。 插入排序（insertionsort）的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开始依次把数据元素按关键字大小插入到已排序的部分排序表的适当位置。 选择排序:选择排序（selectsort） a)开始时设i的初始值为0。 b)如果i c)若A[k]不是这组数据元素中的第一个数据元素（i≠k），则将A[k]与A[i]这两数据元素的位置对调； d)令i=i+1转步骤 b)。 冒泡排序(bubblesort) 的基本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字A[0]和A[1]进行比较。如果前者大于后者，则进行交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数据元素。 堆排序(heapsort): a.对排序表中的数据元素，利用堆的调整算法形成初始堆。 b.输出堆顶元素。 c.对剩余元素重新调整形成堆。 d.重复执行第b、c步，直到所有数据元素被输出。 如果建立的堆满足最大堆的条件，则堆的第一个数据元素A[0]具有最大的关键字，将A[0]与A[n-1]对调，把具有最大关键字的数据元素交换到最后，再对前面的n-1个数据元素使用堆的调整算法，重新建立最大堆，结果把具有次最大关键字的数据元素又上浮到堆顶，即A [0]的位置，再对调A[0]和A[n-2]，…，如此反复执行n-1次，最后得到全部排序好的数据元素序列。 归并排序(mergesort)基本思想是：设有两个有序表A和B，其数据元素个数（表长）分别为n和m，变量i和j分别是表A和表B的当前检测指针；设表C是归并后的新有序表，变量k是它的当前存放指针。开始时i、j、k都分别指向A、B、C三个表的起始位置；然后根据A[i]与B[j]的- 5 - 程序设计挑战式课程设计报告 关键字的大小，把关键字小的数据元素放到新表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[]中，如此反复进行。为了将最后归并结果仍放在数组- 6 - 程序设计挑战式课程设计报告 table.arr[]中，归并趟数应为偶数。如果做奇数趟就能完成时，最后还需要执行一次一趟归并过程，由于这时的归并项长度len>=n，因此在则趟归并中while循环不执行，只做把temptable.arr[]中的数据元素复制到table.arr[]的工作。 基数排序： “基数排序法”（radixsort）则是属于“分配式排序”（distribution sort），基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。具体可以参看后面的代码进行理解。 7、使用说明（运行程序的小型说明书） 看到主菜单后根据主菜单选择所需要的排序方式，然后根据提示输入所需排序的数字数和需排序的数字。若有每一趟的排序结果，没按一次回车键可显示一趟的结果，否则直接输出排序结果。 输出结果后再按一次回车键，再次显示主菜单，可根据需要再次选择排序方式或选择退出，若选择退出程序（over），还需输入完数字数和数字后才能你退出，因此建议若需要退出程序，选择退出选项后再次输入所需排序数为0，方可退出程序。 - 7 - 程序设计挑战式课程设计报告 8、程序开发总结（简要叙述编写本作业的收获与思考） 第一次做大作业，发现了自己很多不足，在程序的优化和逻辑方面还需要继续研究和完善。 同坐这次的程序开发，使我对各排序有了更深入的了解，虽然程序中归并排序和基数排序对于我来说还是很难理解，但为了完善这个程序，决定先运用该排序今后再继续深入研究。 完成该程序设计后，感到深深的满足感，这是第一次写头文件以及第一次写这么长的代码，既是对自己的一次检阅，也是对自己的一次自我提升。 9、运行截图（附上程序运行的截图画面，至少有1幅，截图越翔实得分越高） Windows中抓取当前活动窗口：Alt + Print Screen，抓取全屏：Print Screen。或者使用HyperSnap等软件（百度搜索）。 1、 主菜单 - 8 - 程序设计挑战式课程设计报告 2、 冒泡排序 3、 选择排序 4、 插入排序 - 9 - 程序设计挑战式课程设计报告 5、 快速排序 6、 堆排序 - 10 - 程序设计挑战式课程设计报告 7、 归并排序 8、 基数排序 - 11 - 程序设计挑战式课程设计报告 9、 结束，退出程序 - 12 - 程序设计挑战式课程设计报告 10、源程序（附上程序源代码，若是多个文件，标出文件名） 排序.c #include int A[100000],n,x,y,left,right; char c,ch; L:xianshi(); printf(\"输入要选择的排序：\\n\"); scanf(\"%d\ left=0;right=n-1; printf(\"输入要输入的数字数：\\n\"); scanf(\"%d\ printf(\"输入需要排序的数字：\\n\"); for(x=0;x - 13 - 程序设计挑战式课程设计报告 case 3:{insertionsort(A,n);ch=getchar();break;} case 4:{quicksort(A,n,left,right);ch=getchar();break;} case 5:{heapsort(A,n);ch=getchar();break;} case 6:{mergesort(A,n);ch=getchar();break;} case 7:{radixsort(A,n);ch=getchar();break;} case 8:{printf(\"结束\");return 0;} } goto L; } paixu.h #include void heapadjust(int A[],int i,int length); void merges(int number[],int first,int last,int mid); void merge_sort(int number[],int first,int last); void bubblesort(int A[],int n) //冒泡排序 { int i,j,t,k,m=0; char ch; for(i=0;i 程序设计挑战式课程设计报告 if(A[j] ch=getchar(); printf(\"第%d趟:\ for(k=0;k printf(\"\\n\"); } void selectsort(int A[],int n) //选择排序 { int i,j,t,k,m=0; char ch; - 15 - 程序设计挑战式课程设计报告 for(i=0;i t=A[i]; A[i]=A[k]; A[k]=t; } ch=getchar(); printf(\"第%d趟:\ for(k=0;k printf(\"\\n\"); } - 16 - 程序设计挑战式课程设计报告 void insertionsort(int A[],int n) //插入排序 { int i,j,t,k,m=0; char ch; for(i=1;i A[k+1]=A[k];k--; if(k==-1)break; } A[k+1]=t; ch=getchar(); printf(\"第%d趟:\ for(k=0;k - 17 - 程序设计挑战式课程设计报告 printf(\"\\n\"); } void quicksort(int A[],int n,int left,int right) //快速排序 { int i,j,t,k,m=0; char ch; if(left while(i+1 t=A[i];A[i]=A[j];A[j]=t; } t=A[left],A[left]=A[j],A[j]=t; ch=getchar(); for(k=0;k 程序设计挑战式课程设计报告 if(A[k]>A[k+1]) m++; if(m==right-left) return; //若已为降序则退出 quicksort(A,n,left,j-1); quicksort(A,n,j+1,right); } printf(\"\\n\"); } void heapsort(int A[],int length) //堆排序 { int i,j,t,k,m=0; char ch; for(i=length/2-1;i>=0;--i) heapadjust(A,i,length); for(i=length-1;i>0;--i) { A[i]=A[0]^A[i]; //实际为二者交换值 A[0]=A[0]^A[i]; A[i]=A[0]^A[i]; heapadjust(A,0,i); ch=getchar(); printf(\"第%d趟\ for(k=0;k 程序设计挑战式课程设计报告 printf(\"%d \ m=0; for(k=0;k printf(\"\\n\"); } void mergesort(int A[],int n) //归并排序 { int i; merge_sort(A,0,n-1); printf(\"**无法显示排序过程**\\n排序结果:\"); for(i=0;i int temp[10][10]={0}; int order[10]={0}; int i,j,k,q,lsd; - 20 - 程序设计挑战式课程设计报告 k=0;q=1; while(q<=n) { for(i=0;i temp[lsd][order[lsd]]=A[i]; order[lsd]++; } for(i=0;i for(j=0;j - 21 - 程序设计挑战式课程设计报告 printf(\"**无法显示排序过程**\\n排序结果:\"); for(i=0;i int child,temp; for(;2*i+1 if(child temp=A[i]; A[i]=A[child]; A[child]=temp; } else break; } - 22 - 堆调整 程序设计挑战式课程设计报告 } void merges(int number[],int first,int last,int mid) //归并算法 { int number_temp[10]={0}; int i=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] - 23 - 程序设计挑战式课程设计报告 number[i] = number_temp[j]; } void merge_sort(int number[],int first,int last) { int mid=0; if(first merge_sort(number,first,mid); merge_sort(number,mid+1,last); merges(number,first,last,mid); } } display.h #include printf(\" ************************************\\n\"); printf(\" * 1 bubble sort *\\n\"); printf(\" * 2 select sort *\\n\"); printf(\" * 3 insertion sort *\\n\"); printf(\" * 4 quick sort *\\n\"); - 24 - 程序设计挑战式课程设计报告 printf(\" * 5 heap sort *\\n\"); printf(\" * 6 merge sort *\\n\"); printf(\" * 7 radix sort *\\n\"); printf(\" * 8 over *\\n\"); printf(\" ************************************\\n\"); } - 25 -
因篇幅问题不能全部显示，请点此查看更多更全内容