《数据结构课程设计内部排序算法性能分析.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计内部排序算法性能分析.docx（16页珍藏版）》请在三一文库上搜索。
1、“数据结构力课程设计报告（内部排序算法性能分析）学生姓名: 指导教师: 所在系: 所学专业: 年 级:目录1、 需求分析 -1 -1.1、 选题要求-.1 -1.2、 选题的意义及背景 -.1 -1.3、课程设计目标 -.1 -2、概要设计 -2 -2.1、原始数据-2 -2.2、输出数据-2 -2.3、数据处理-2 -2.4、 逻辑结构及物理结构 .-.3-2.5、系统的模块划分及模块功能 -.32.5.1 主程序模块 -3 -2.5.2可排序表单元模块 -3 -2.6、模块的测试数据-.4 -3、详细分析 -5 -4、调试分析 -6 -5、用户手册 -9 -6、测试结果 -10 -6.1测
2、试用例及选择原因 .-.10-6.2测试结果.-.1 0-7、总结 -12 -8、参考文献 -13 -9、小组人员分工 -13 -致谢 -13 -1、需求分析1.1、选题要求对各种排序算法进行定量的性能分析。1.2、选题的意义及背景排序是计算机程序设计中的一种重要操作。 它的功能是将一个数据元素的任 意序歹0,重新排歹0成一个按关键字有序的序歹0。内部排序的方法很多，但是就其全面性能而言，彳艮难提出一种被认为是最好 的方法，每一种方法都有各自的优缺点， 适合在不同的环境下使用。如果按排序 过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序，交换排序，选择排序，归并排序和记数排序等
3、五类。此实验通过对起泡排序、直插排序、选择排序、快速排序、归并排序这几种 内部排序算法进行比较，能使我们更好的掌握这些排序的基本思想及排序算法。 通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、 存储结构及相 应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用丁解决实际问题，培养我们的动手能力。1.3、课程设计目标本课程设计对以下内部排序算法进行比较： 起泡排序、直插排序、选择排序、 快速排序、归并排序。待排序表的元素关键字为整数，用不同的测试数据做测试比较。比较的指标 为关键字的比较次数和关键字的移动次数。 最后用图、表格数据汇总数据，以便 对这些
4、内部排序算法进行性能分析。-14 -2、概要设计2.1、原始数据用户输入记录的个数，数据由随机数产生器生成。2.2、输出数据产生的随机数分别用起泡排序、直插排序、选择排序、快速排序、归并排序 这些排序方法进行排序，输出关键字的比较次数和移动次数。2.3、数据处理循环50次将随机数保存在数组中记录关键字的比较 次数和移动次数输出关键字的比较次 数、移动次数的平均值2.4、逻辑结构及物理结构以顺序表为存储结构(物理结构)typedef struct(int key; / 关键字ElemType;typedef struct(ElemType *elem;int length;/ 数据元素个数 Sq
5、List;2.5、系统的模块划分及模块功能系统分为两个模块2.5.1主程序模块void main ()2.5.2可排序表单元模块A. 选择排序void SelectSort(SqList &L)B. 起泡排序void BubbleSort(SqList &L)C. 直接插入排序void InsertSort(SqList &L)void BeforeSort()void display(int m,int n)D. 快速排序int Partition(SqList &L,int low,int high)void QSort(SqList &L,int
6、low,int high)void QuickSort(SqList &L)E. 归并排序2.6void MergeSort(SqList &L)模块的测试数据以关键字的数目分别为10, 100, 1000为例，作为测试数据3、详细分析(1) 选择排序基本思想：在待排序的一组数据元素中，选出最小的一个数据元素与第一个 位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数 据元素交换，循环到只剩下最后一个数据元素为止。(2) 起泡排序基本思想：相邻的两个元素进行比较，将小的调到前面，大的调到后面。(3) 直接插入排序待排序的记录放在数组R0n-1中排序过程中某一
7、时刻，R被划分成两个子 区问R0i-1(有序和)Ri n-IK无序)。直接插入的基本操作是将当前无序 区的一个记录Ri插入到有序区R0i-1中适当的位置(4) 快速排序基本思想：在待排序的数组的n个元素中取一个元素(一般取第一个)，将其 移动到这样的位置：在其之前的元素的值都小丁它，在其之后的元素都大丁它， 这样是一趟快速排序；然后对数组的两个部分进行同样的操作， 直到每部分只有 一个记录为止；总之，每趟使表的第一个元素放在适当位置，将表两分，再对两 子表进行同样的递归划分，直至划分的子表长度为1!(5) 归并排序基本思想：将两个或两个以上的有序表组成一个新的有序表。4、调试分析(1) 刚开始
8、进行调试时，有些排序方法不能实现，我就对不能实现的排序 进行分析，对产生的语法错误进行了及时的改正， 以至所有的排序算法能够顺利 的实现。画飞八实训'数据结构6T8Debug678. eze请输入你要输入的个数:项 起植排序_乳输町移动次数为皆瞽入你要输入的个薮油 请新入你套输入的个薮濒 or39移动次数为36移动次数为一厂一 39移动次数为请输入你要输入的个B：1047121836移动次数为Press any key to continue(2) 考虑不周全，每种排序算法所使用的随机数并不相同，这样便使得得到的关键字的比较次数和移动次数不具有可比性。改后的程序便解决了这个问M VJ&
9、#39;DimgV；- eV n X欢迎T井入内滞排序算法，件俳分和I系窕- 请输入记录的个数=皿比较次撤为361 H比较次裁为起泡排序81移动次裁为12比较次数为直插排序*移劾次数为比恢次数为快速排序，45移动犹教为±8比较次楚为归井排序，36惨砌次数为21Pi'ess mny ke 7 to coni; ±nue(3) 从上面的显示可以看出，直插排序的移动次数为1 (只有数据是正序的 时候，才是为1),经检查程序存在问题。随机数在经过选择排序后，已经变为正 序的数据，后面的排序方法是对以上正序数的排序。 为此专门设置一个数组，存 取随机数。但是改后的程序出现了下
10、面的状况。编译正确，执行不了。(4) 上网查询执行不了的原因，网上是这样讲的：Window寸系统设置错误，提示:)WA5FzPLwlibcmtd.lib(crt0.obj) : error LNK2001: unresolved external symbol_main *+oJ(e+4f'1Window颜目要使用Window/系统，而不是Console,可以这样设置：*A'y#/D+gz !DF-%3|Project -> Settings->选择"Link"届性贞,Qo!在Project Options 中将/subsystem:consol
11、e 改成/subsystem:windowsT'H.k"YXn?t*但是自己的机子的设置却改不了。网上有人建议用CodeBlocks这个程序进行 执行，安装这个程序，编译执行后，得到下面的结果。有效的解决了上面的问题。*C: Docu>ents and Sett ingsAd>inist rat or桌面sort. eze X欢迎进入内部排序算法性能分析系统 -请输入记录的个数选择排序比较次数为36移动次数为18比较次数为起泡排序81移动次数为63比较次数为直插排序9移动次数为10比较次数为快速排序40移动次数为18比较次数为归并排序36移动次数为23(5) 在老
12、师的指导下，找到了无法执行的原因。主函数定义错误将 void addlist(SqList &L) 改为Void main()( SqList L;问题解决。5、用户手册(1)本程序的运行环境为DOSS作系统(2)进入演示程序后，即显示文本方式的用户界面C 二 XDocuMeikt s and Se±t ingsAdMxnist rat oisort .-口 X欢迎进入内部排序算法性能分析系统 请输入记求的个数、(3)演示程序以人机对话的形式进行。只要输入记录的个数，程序便产生50组随机数，显示通过选择排序、起泡排序、直插排序、快速排序、归并排序对随机数进行排序时，关键字的比
13、较次数和移动次数的平均值， 从而直观的比较 各种内部排序算法的优劣。国I *C s PociineM s and Sett in£sAdBinifftirat or桌面-|o|x.欢迎进入内部排序算法性能分析系统比较次数为移动次数为比较次数为比较次数为比较次数为比较次数为起泡排序移动次数为t直插排序匕快速排序归并排序移动次数为移威次数为移动次数为6、测试结果6.1测试用例及选择原因记录数分别输入10、100、1000,之所以想用这三个记录数测试，是想测试 用选择排序、起泡排序、直插排序、快速排序、归并排序这五种排序方法，在记 录较小和较大时，关键字的比较次数和移动次数，用以直观的分析
14、它们的性能。6.2测试结果测试的结果如下表：(注：此数据为50组数据的平均值)记录数的个数关键字选择排序起泡排序直插排序快速排序归并排序10比较次数368194036移动次数1868121823100比较次数4851980199624688移动次数281739415643274091000比较次数49850199800199984879984移动次数2974749592175354476854336.3结论关键字选择排序起泡排序直插排序快速排序归并排序记录数比较次数较少最多最少较少较少较小移动次数较少最多较少较少较少比较次数较少最多最少较少较少较大移动次数最少最多较多较少较少由上表可以得出：(
15、1) 选择排序的比较次数较少且为定值，但由丁它在排序过程中要先查询、再 安置，所以性能上不够稳定。(2) 起泡排序的比较次数和移动次数在这五种排序方式中最多，所以起泡排序 的排序性能相对丁其他排序要低好多。(3) 直插排序的比较次数和移动次数相比较丁其他几种排序次数要少，所以效 率相比较而言较高，性能较高，且较稳定。从整体上来讲性能较其他几种排序较|i=ij o(4) 快速排序在这几种排序当中从比较次数较少的，移动次数多丁选择排序但 低丁其他三种排序，且其过程是先定一个基准，大小各放一边，再分别对两边多 次操作，达到整体有序，所以性能上来看是最快最好的，但是不够稳定。(5) 归并排序的比较次数
16、和移动次数相当，且较小。在记录数较大时，关键字的比较次数和移动次数较少，在使用它对两个己有序的序列归并，将有无比的优 势。由此可见上述内部排序方法，每一种方法都有各自的优缺点，适合在不同的环境 下使用。通过这个结论，我们可以找到一些内部排序方法选择的规则。规则如下：(1) 当n较小时：可采用直接插入排序和直接选择排序。(2) 当记录规模小时，可选择直接插入排序；当记录规模大时，可选择直接选择排序，因为直接插入排序所需的记录移动操作比直接选择排序多。(3) 当记录基本有序时：可采用直接插入排序和冒泡排序。(4) 当n较大时：可采用快速排序和归并排序。7、总结在这一周的数据结构课程设计中，我们的题
17、目是：内部排序算法性能分析，通 过该课程设计，我们加深了对内部排序算法的理解，对内部排序算法的基本运算 的实现有所掌握，对课本中所学的各种数据结构进一步理解和掌握 ，学会了如何 把学到的知识用丁解决实际问题，锻炼了自己动手的能力。一个人的力量是渺小的，在课程设计中我们学会了团结协作。 在课程设计时 遇到了很多的问题，大家便一起讨论解决的方法，锻炼了我们的协作能力。为今 后在学习工作中能更好的发展打下了坚实的基础。一周的课程设计很短暂，但其间的内容是很充实的，在其中我们学习到了很 多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题、解决问题的 能力，并学会了如何将所学的各课知识融会，组织
18、，来配合学习，这一周让我们 受益匪浅。8、参考文献1 .严蔚敏，吴伟民，数据结构（C语言版），活华大学出版社,20092 .严蔚敏，吴伟民，数据结构题集（C语言版），活华大学出版社,20099、小组人员分工组长：王乐组员：韩守飞、时良荣分工：王 乐：主程序、归并排序、报告撰写时良荣：选择排序、直插排序、数据记录韩守飞：起泡排序、快速排序、数据记录致谢在这里感谢我们的指导老师陈少军老师，他在我们的课程设计过程中提出了 指导性的方案和架构，并在设计过程中不断指引我们发现错误，改正错误。并教 育我们要思路开阔，发散思维，考虑问题全面细致，并指引我们阅读相关的资料 和书籍，不断完善自己的程序，使我们的课程设计能够顺利完成。