毕业设计_工学_高等教育_教育专区 10页

数据结构中排序方法研究毕业设计班级：计机132姓名：学号：指导教师：孙永林2016-3-18计算机应用（电子商务）\n广东交通职业技术学院目录内容摘要1引言1正文1一、直接插入排序1二、Shell排序2三、直接选择排序3四、冒泡排序3五、快速排序4六、堆排序4七、基数排序5程序运行结果以及结果分析6对程序结果的评价：7参考文献（或资料）7附录心得7\n内容摘要数据结构中排序方法研究主耍是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们Z间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要棊础，广泛的应用于信息学、系统工程等各种领域。排序在计算机程序设计中非常重要，各种排序方法各有其优缺点，适用场合也不同。本文从多个方面对各种内排序方法进行全面的比较和分析，最后给出综合结论。关键词：排序方法比较结论引言排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元索的任意序列，重新排列成一个按关键字有序的序列。排序算法是在整个计算机科学与技术领域上广泛被使用的术语。排序算法是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。排序是计算机科学中最重要的研究问题它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具冇广泛的应用。由于它固冇的理论上的重要性,其功能是将一个数据元素的任意序列重新排列成一个按关键字有序的序列。随着计算机技术的FI益发展，其应用早已不局限于简单的数值运算。阳涉及到问题的分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。排序算法的学习就是为以后利用计算机资源高效地开发II擞值处理的计算机程序打下坚实的理论、方法和技术棊础。正文一、直接插入排序1•原理假设待排序的n个记录｛RO,R1,…，Rn｝顺序存放在数组中，直接插入法在插入记录Ri(i=l,\n2,…，n・l)时，记录被划分为两个区间［RO,Ri-l］和［Ri+l,Rn・：l］,其中，前一个子区间已经排好序，后一个了区间是当前未排序的部分，将关键码Ki与Ki-lKi-2,…，K0依次比较，找出应该插入的位置，将记录Ri插，然麻将剩下的"个元素按关键词人小依次插入该有序序列,没插入一个元素后依然保持该序列有序，经过"趟排序后即成为有序序列。每次将一•个待排序的记录，按其关键字大小插入到前而已经排好序的子文件中的适当位置，直到全部记录插入完成为止。2.时间复杂度分析肓接插入排序算法必须进行ml趟。最好情况下，即初始序列何序，执行ml趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1),移动元素次数是2(n-l)o因此最好情况下的吋间复朵度就是0(n)o最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为0(n2)o二、Shell排序1.原理Shell排序又称缩小增量排序‘Shell排序法是以创建者DonaldShell的名字命名的.Shell排序法是对相邻指定距离(称为间隔)的元索进行比较，已知到使用当前间隔进行比较的元索都按顺序排序为止.Shell把间隔缩小一半，然后继续处理，当间隔最终变为1,并且不再出现变化时,Shell排序也就完成了其处理过程.先取一个整数dlvn,把全部记录分成dl个组，所有距离为dl借数的记录放在一组中，先在各组内排序;然后去d2=k2iILki>=k2i+lo若将此序列所存储的向量R[l---n]看作是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完金二叉树:树中非叶结点\n的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。根结点（亦称为堆顶）的关键字是堆里所冇结点关键字中最小者的堆称为小根堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最人者，称为人根堆。2•时间复杂度分析堆排序的时间，主要山建立初始堆和反复重建堆这两部分的吋间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为0（nlogn）e堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度O（nlogn）。七、基数排序基数排序和通帘的排序算法并不走同样的路线。它是一•种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上,然后再映射回去,这是非常麻烦的事悄,因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。下而是一个总的表格，大致总结了我们常见的所有的排序算法的特点。序号排序法平均时间最差情形稳定度额外空间备注1冒泡法0(n2)0(n2)稳定0(1)n小时较好2交换法0(n2)0(n2)不稳定0(1)n小时较好3选择法0(n2)0(n2)不稳定0(1)n小吋较好4插入法O(n2)0(n2)稳定0(1)大部分已排序时较好5基数法O(logRB)O(logRB)稳定0(n)B是真数（0-9）,R是基数（个十百）6Shell法O(nlogn)O(ns)1<2不稳定0(1)s是所选分组7快速法O(nlogn)0(n2)不稳定O(nlogn)n大时较好8归并法O(nlogn)O(nlogn)稳定0(1)n大时较好9堆排法O(nlogn)O(nlogn)不稳定0(1)n人时较好\n程序运行结果以及结果分析-、下图是对随机生成的10000个数进行排序，可以看出快速排序法耗时最少而直接插入排序耗时最多，堆排序和快速排序差不多。c：\・C:\windows\system32\cmd.exe733627007730712584907354528283545487862949654118875025675890867176582255925?55271536747221701866290133594399407843427044187184444332185504459816695602171785599172052955843937786862667758275253166385659285881039597548113074977465592160729439952762177037690139412447237181861695148191482553918487673508685610620275794920530457477836468871482933999853591005003440873243834009387061956055126868?44334880812115804731316312846028192377057464425925954?5627880?19372298656130395528168269418949994829318547651899065599liB耗时询.申序耗时=1.247000seconds206314702638654343111?70905?28304445904579402488367032300519??58018671698422026249896251755540277732025864812496086985477656247966821319378730493426622282146574811727713839264924618433404214297319178201313310087686894923172410706538461341138891827234249433644690377789134092847115710385652730197025728271724638518986684152726617359822247651113859477069157534751816129387261376375809601929614573956910926746077271299029129758842591115343734088273373844726468044025657827194607021116070599950149399975243428427030_38999608512A冒泡排序耗时：0.483000seconds耗时238000seconds004000seconds0；：0.041000seconds0.015000secondsH：0-005000seconds二、下图是对20000个随机数进行的排序，可以看出得出了和上述一样的结果。C:\windows\system32\cmd.exe83115332455714873688447611341333466218198481875504143112451171016325199610746296915261370811996133960727989109661856219729163841312447131008746031105915334484668531924083934721186630429622592895|7463952247304960152111610080271133516130612510760577513833151541679345819232280915400940819699368298161165815471095060881729343101905?144246655107115166588146604800913464098591591214516809112937909630126324291185941554844187090106931205611054481023941237323879141861146169300889357124118723641777603203140308861751012649132906489522670714?101025155867818129331773007899372412174106388774828106514479187218922176671272889834105979145391913336601007335401081826051772073671239666612764379914361120230041228235711446517502265371432331285470914672686624991712285610116148221659214258793965001137090175391118965410973183171566250779132041151081038312648685966611264770678541685133811633613494020774248019213579031146926826063374597021092510978289718314181437571050184581034167611861211928168061712157431987010114270141911180162999680316799163633486905?25431834625459231冒泡排序耗时.305000secondsS耗时二丄.005000seconds・764000seconds：0.006000seconds103000seconds选择独….剩0・按任Sw一\n：0.024000seconds008000seconds瞥排意键继续•…捜狗卅苜猛关法半：对程序结果的评价:经过比较我们发现，当规模不断增加时，各种算法Z间的差别是很人的。这七种算法中，快速排序耗时是最少的。也是最快的一种排序方法。堆排序和快速排序差不多，属于同一个数量级。直接选择排序是耗时最多的。通过这次作业我学到了很多东西：①巩固和加深了対数据结构的理解，提高综合运用本课程所学知识的能力。②通过口己编写的程序对各种排序性能的比较让我更深入理解了他们的应用。参考文献（或资料）⑴数据结构与算法分析：C语言描述（原书第2版）［美］维斯著，冯舜玺译机械工业出版社⑵数据结构与算法分析Java语言描述（原书第3版）［美］马克・艾伦・维斯；陈越机械工业出版社［3］《数据结构一C++实现》科学教育出版社附录心得在进行为期一个星期的课程设计中，最终完成了算法。这期间，遇到的各种麻烦也都相继解决。从这次实践中，我意识到自己还冇很多不足Z处。首先先说一下基木的。对于各种排序算法的过程还是不够熟悉，进行编程时还需要翻书查找，对于这一点，只能说对数据结构的学习还不够扎实，还需要在以后的学习中多多注意c卄语言的学习和数据结构的相关知识。其次，就是对丁•错误的处理，不能得心应手，不能正确处理一些简单的错误。对于逻辑\n上的错误，不能够立即找到出错点，往往需要向同学请教才能找出错误，并且改正。从总体上说，整个代码的实现还是存在不足的，例如木程序不能判断字符数人于1的字符串，没有相应排序的性能分析（如空间复杂度，时间复杂度），等等。从这点看，说明自己的程序还是不够完善，不能做到十全十美，希望以后能有所修正。总而言之，从这次的实践中我学到了很多东西，在以后的学习生活中要多多注意整顿自己的学风，严谨踏实的面对学习之屮的问题。