《各种排序算法时间性能的比较讲解》由会员分享，可在线阅读，更多相关《各种排序算法时间性能的比较讲解（12页珍藏版）》请在金锄头文库上搜索。
1、实训报告实训题目:各种排序算法时间性能的比较学 院：计算机科学与技术学院专 业： 软件工程班 级：142学 号：1400170269学生姓名：莫磊指导教师：蔡丽2016年3月15日一、实训目的及要求数据结构是计算机课程的一门重要的基础课，它的教学要求大致有三个重要方面： 其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为数据选择适当的 物理结构和逻辑结构；其二，根据结构，选择适当的算法，并初步掌握算法的时间分 析和空间分析；其三，学习复杂的程序设计。本综合实训利用Visual Studio 2008集 成编程环境为实践工具，通过上机实践培养学生分析具体问题、解决实际问题的能力, 训练
2、和培养学生的数据抽象能力和程序设计的能力。数据结构是一门实践性较强的课程，以培养学生的数据抽象能力和程序设计的能 力为目的。在实训时应注重培养学生的实际操作能力。本综合实训安排了 18学时的实 验课时，具体要求如下：1. 学习和理解每个实训题目的基本理论和方法；2. 掌握每个实验的实现步骤和关键技术；3. 准备好实验所需要的资源和文档；4. 上机实现程序，得到通过调试的正确程序。5. 根据每个实验的不同要求，完成实验报告的word文档。二、实训环境Windows XPVisual Studio 2013三、实训内容(1) 设计并实现上述各种排序算法；(2) 产生正序和逆序的初始排列分别调用上述
3、排序算法，并比较时间性 能；(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。(4) 对各种排序方法(直接插入排序、希尔排序、起泡排序、直接选 择排序)的时间性能进行比较。四、算法描述及实训步骤上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过 程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不 同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。五、总结及心得体会直接选择排序算法是对冒泡排序的改进，这种方法是在参加排序数组 中找出最小（或最大）的数据元素，使它与第一个元素中的数据相互交换 位置然后再在余下的元素中找出最小（或最大）的数据元素与
4、第二个元素 中的元素交换位置，以此类推直到所有元素成为有序序列。六、实训结果=输岀希尔正序排序后数据如下=0123455668111112161618182122232323242626272729292929313334353536373738383940404141414142424244444546474748485053535456575859616262646464666767686969707173767878818282848890909191929394959599比较的次数为：5脱移动的次数为：45701234556681111121616181821222323232426
5、26272729292929313334353536373738383940404141414142424244444546474748485053535456575859616262646464666767686969707173767878818282848890909191929394959599=输岀希尔逆序排序后数据如下=比较的次数为：502移动的次数为：457输岀冒泡正序排序后数据如下0123455668111112161618182122232323242626272729292929313334353536373738383940404141414142424244444546
6、474748485053535456575859616262646464666767686969707173767878818282848890909191929394959599比较的次数为:4797移动的次数为:2609给山 曰右:卅盒扫匕盒 二粉+丘右口卞目把逆序徘呼后裁如卜999595949392919190908884828281787876737170696968676766646464626261595857565453535048484747464544444242424141414140403938383737363535343331292929292727262624232
7、3232221181816161211118665543210比较的次数为:4947移动的次数为:2297输岀直接插入正序排序后数据如下0123455668111112161618182122232323242626272729292929313334353536373738383940404141414142424244444546474748485053535456575859616262646464666767686969707173767878818282848890909191929394959599比较的次数为：99移动的次数为:2609古晋 生 古后件 ；.比序钊匕由 二曲k+巳
8、右口丁一-WlIj亘按宙丿予排厅后JxiE如卜99959594939291919090888482828178787673717069696867676664646462626159585756545353504848474746454444424242414141414040393838373736353534333129兀9Q9797加加煦煦二二二输出直接选择正序排序后数据如下二二0123455668111112161618182122232323242626272729292929313334353536373738383940404141414142424244444546474748
9、485053535456575859616262646464666767686969707173767878818282848890909191929394959599比较的次数为:4950移动的次数为：94=二输出直接选择逆序排序后数据如下二二 二9995959493929191909088848282817878767371706969686767666464646262615958575654535350484347474645444442424241414141404039383837373635353433312929292927272626242323232221181816161
10、211118665543210比较的次数为:4950移动的次数为：97所有排序的比较次数和移动次数如下:冒冒直直直直序序序序 正逆正逆 .序.序.序 -. A. . A. - P 丰$. 正正正逆插插囲囲 尔尔泡泡接接接接比较次数为：503移动次数为：4即 比较次数为:503移动次数为：457 比较次数为:4797移动次数为：2609 比较次数为:4947移动次数为：毙折 比较次数为:99移动次数为:2609 比较次数为:胆移动次数为：2297 比较次数为:4950移动次数为：94 比较次数为：4950移动次数为：97七、源代码:#includest dio.h#includest dlib.h#includeti me.h/正序希尔排序void xiEr(in t num, int n,
