数据结构课程设计(内部排序算法性能分析).doc

“数据结构”课程设计报告（内部排序算法性能分析）学生姓名： 指导教师：所 在 系：所学专业：年 级：- 13 -目录1、需求分析11.1、选题要求11.2、选题的意义及背景11.3、课程设计目标12、概要设计22.1、原始数据22.2、输出数据22.3、数据处理22.4、逻辑结构及物理结构32.5、系统的模块划分及模块功能32.5.1主程序模块32.5.2可排序表单元模块32.6、模块的测试数据43、详细分析54、调试分析65、用户手册96、测试结果106.1测试用例及选择原因106.2测试结果107、总结128、参考文献139、小组人员分工13致 谢131、需求分析1.1、选题要求对各种排序算法进行定量的性能分析。1.2、选题的意义及背景排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序，交换排序，选择排序，归并排序和记数排序等五类。此实验通过对起泡排序、直插排序、选择排序、快速排序、归并排序这几种内部排序算法进行比较，能使我们更好的掌握这些排序的基本思想及排序算法。通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。1.3、课程设计目标本课程设计对以下内部排序算法进行比较：起泡排序、直插排序、选择排序、快速排序、归并排序。待排序表的元素关键字为整数，用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。最后用图、表格数据汇总数据，以便对这些内部排序算法进行性能分析。2、概要设计2.1、原始数据用户输入记录的个数，数据由随机数产生器生成。2.2、输出数据产生的随机数分别用起泡排序、直插排序、选择排序、快速排序、归并排序这些排序方法进行排序，输出关键字的比较次数和移动次数。2.3、数据处理主程序产生1组随机数起泡排序直插排序快速排序归并排序选择排序记录关键字的比较次数和移动次数将随机数保存在数组中循环50次输出关键字的比较次数、移动次数的平均值 2.4、逻辑结构及物理结构以顺序表为存储结构（物理结构）typedef struct int key; /关键字ElemType;typedef struct ElemType *elem; int length;/数据元素个数SqList; 2.5、系统的模块划分及模块功能MainSelect Sort Bubble Sort Insert Sort Quick Sort Merge SortOutput quick系统分为两个模块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 low,int high)void QuickSort(SqList &L)E归并排序 void MergeSort(SqList &L)2.6、模块的测试数据以关键字的数目分别为10，100，1000为例,作为测试数据。3、详细分析（1）选择排序基本思想：在待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止。（2）起泡排序基本思想：相邻的两个元素进行比较，将小的调到前面，大的调到后面。 （3）直接插入排序待排序的记录放在数组R0n-1中排序过程中某一时刻，R被划分成两个子区间R0i-1 (有序和)Rin-1(无序)。直接插入的基本操作是将当前无序区的一个记录Ri插入到有序区R0i-1中适当的位置（4） 快速排序 基本思想：在待排序的数组的n个元素中取一个元素(一般取第一个)，将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，这样是一趟快速排序；然后对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子表长度为1！（5）归并排序基本思想：将两个或两个以上的有序表组成一个新的有序表。4、调试分析（1）刚开始进行调试时，有些排序方法不能实现，我就对不能实现的排序进行分析，对产生的语法错误进行了及时的改正，以至所有的排序算法能够顺利的实现。（2）考虑不周全，每种排序算法所使用的随机数并不相同，这样便使得得到的关键字的比较次数和移动次数不具有可比性。改后的程序便解决了这个问题。（3）从上面的显示可以看出，直插排序的移动次数为1（只有数据是正序的时候，才是为1），经检查程序存在问题。随机数在经过选择排序后，已经变为正序的数据，后面的排序方法是对以上正序数的排序。为此专门设置一个数组，存取随机数。但是改后的程序出现了下面的状况。编译正确，执行不了。（4）上网查询执行不了的原因，网上是这样讲的：Windows子系统设置错误, 提示: )WA5FzPLw libcmtd.lib(crt0.obj) : error LNK2001: unresolved external symbol _main *+oJ(e+ 4f'1 Windows项目要使用Windows子系统, 而不是Console, 可以这样设置: *'y#/D+g z !DF-%3| Project -> Settings -> 选择"Link"属性页, Qo! 在Project Options中将/subsystem:console改成/subsystem:windows TH.k"Y Xn?t*但是自己的机子的设置却改不了。网上有人建议用CodeBlocks这个程序进行执行，安装这个程序，编译执行后，得到下面的结果。有效的解决了上面的问题。（5）在老师的指导下，找到了无法执行的原因。主函数定义错误。将void addlist(SqList &L)改为Void main() SqList L;问题解决。5、用户手册（1）本程序的运行环境为DOS操作系统（2）进入演示程序后，即显示文本方式的用户界面。（3）演示程序以人机对话的形式进行。只要输入记录的个数，程序便产生50组随机数，显示通过选择排序、起泡排序、直插排序、快速排序、归并排序对随机数进行排序时，关键字的比较次数和移动次数的平均值，从而直观的比较各种内部排序算法的优劣。6、测试结果6.1测试用例及选择原因记录数分别输入10、100、1000，之所以想用这三个记录数测试，是想测试用选择排序、起泡排序、直插排序、快速排序、归并排序这五种排序方法，在记录较小和较大时，关键字的比较次数和移动次数，用以直观的分析它们的性能。6.2测试结果测试的结果如下表：（注：此数据为50组数据的平均值）记录数的个数关键字选择排序起泡排序直插排序快速排序归并排序10比较次数368194036移动次数1868121823100比较次数4851980199624688移动次数281739415643274091000比较次数49850199800199984879984移动次数2974749592175354476854336.3结论关键字选择排序起泡排序直插排序快速排序归并排序记录数比较次数较少最多最少较少较少较小移动次数较少最多较少较少较少比较次数较少最多最少较少较少较大移动次数最少最多较多较少较少由上表可以得出：（1）选择排序的比较次数较少且为定值，但由于它在排序过程中要先查询、再安置，所以性能上不够稳定。（2）起泡排序的比较次数和移动次数在这五种排序方式中最多，所以起泡排序的排序性能相对于其他排序要低好多。（3）直插排序的比较次数和移动次数相比较于其他几种排序次数要少，所以效率相比较而言较高，性能较高，且较稳定。从整体上来讲性能较其他几种排序较高。（4）快速排序在这几种排序当中从比较次数较少的，移动次数多于选择排序但低于其他三种排序，且其过程是先定一个基准，大小各放一边，再分别对两边多次操作，达到整体有序，所以性能上来看是最快最好的，但是不够稳定。（5）归并排序的比较次数和移动次数相当，且较小。在记录数较大时，关键字的比较次数和移动次数较少，在使用它对两个己有序的序列归并，将有无比的优势。由此可见上述内部排序方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。通过这个结论，我们可以找到一些内部排序方法选择的规则。规则如下：（1）当n较小时：可采用直接插入排序和直接选择排序。（2）当记录规模小时，可选择直接插入排序；当记录规模大时，可选择直接选择排序，因为直接插入排序所需的记录移动操作比直接选择排序多。（3）当记录基本有序时：可采用直接插入排序和冒泡排序。（4）当n较大时：可采用快速排序和归并排序。7、总结在这一周的数据结构课程设计中,我们的题目是:内部排序算法性能分析,通过该课程设计,我们加深了对内部排序算法的理解,对内部排序算法的基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。一个人的力量是渺小的，在课程设计中我们学会了团结协作。在课程设计时遇到了很多的问题，大家便一起讨论解决的方法，锻炼了我们的协作能力。为今后在学习工作中能更好的发展打下了坚实的基础。一周的课程设计很短暂，但其间的内容是很充实的，在其中我们学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题、解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，这一周让我们受益匪浅。8、参考文献1. 严蔚敏，吴伟民， 数据结构（C语言版），清华大学出版社,20092. 严蔚敏，吴伟民， 数据结构题集（C语言版），清华大学出版社,20099、小组人员分工组长：王乐组员：韩守飞、时良荣分工：王 乐：主程序、归并排序、报告撰写时良荣：选择排序、直插排序、数据记录韩守飞：起泡排序、快速排序、数据记录致 谢在这里感谢我们的指导老师陈少军老师，他在我们的课程设计过程中提出了指导性的方案和架构，并在设计过程中不断指引我们发现错误，改正错误。并教育我们要思路开阔，发散思维，考虑问题全面细致，并指引我们阅读相关的资料和书籍，不断完善自己的程序，使我们的课程设计能够顺利完成。