课程设计任务书--常用排序算法的比较.doc

课程设计任务书--常用排序算法的比较.doc

  1. 1、本文档共31页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
重庆科技学院 课程设计任务书 设计题目:常用排序算法的比较 学生姓名 *** 课程名称 数据结构课程设计 专业班级 ***** 地 点 计算机基础自主学习中心 起止时间 2011.11.16-12.5 设计内容及要求 利用随机函数产生N个随机整数,多种方法对这些数进行排序。 要求: 1)采用的有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序并把排序后的结果保存在不同的文件中。 2) 统计每一种排序的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的法。000 个以上的随机整数,并保存在文本文件中。排序后的数据和所需的时间也保存在各自的txt文件中。 进度 要求 参考资料 1.严蔚敏 吴伟民 著, 数据结构,清华大学出版社,2007.3 2.李春葆 著,数据结构教程,清华大学出版社,2005.1 3. Richard F.Gilberg Behrouz A.Forouzan, 数据结构的C++伪码实现(英文版),人民邮电出版社,2002.1 其它 说明 1.本表应在每次实施前一周由负责教师填写二份,院系审批后交院系办备案,一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的,在设计内容、参数、要求等方面应有所区别。 教研室主任: 指导教师: 2011年 11月 16日 摘要 排序算法是数据结构学科经典的内容,其中内部排序现有的算法有很多种,泡排序,直接插入排序,简单选择排序,快速排序,堆排序各有特点对排序算法的分析可以遵循若干种不同的准则,通常以排序过程所需要的算法步数作为度量,有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间,例如,当键是较长的字符串时,常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录,且记录都很大时,还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。利用随机函数产生N个随机整数,多种方法对这些数进行排序。 摘要 I 1 设计内容和要求 1 1.1 设计内容 1 1.2 设计要求 1 2 需求分析 2 2.1 直接插入排序 2 2.2 希尔排序 2 2.3 快速排序:(递归和非递归) 2 2.4 堆排序 3 3 概要设计 4 3.1 头文件 4 3.2 ADT 4 3.3 各种操作函数: 4 3.4 主函数 5 4 详细设计 6 4.1 主函数 6 4.2 直接插入排序 7 4.3 希尔排序 9 4.4 起泡排序 10 4.5 快速排序 11 4.6 选择排序 13 4.7 堆排序 15 4.8 归并排序 18 5 系统测试 21 5.1 系统操作 21 5.2 测试数据 23 6 总结 26 致谢 27 参考文献 28 1 设计内容和要求 1.1 设计内容 利用随机函数产生N个随机整数,多种方法对这些数进行排序。1) 分别采用的有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序并把排序后的结果保存在不同的文件中。 2) 统计每一种排序的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的法。 2 需求分析 2.1 直接插入排序 思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列. 2.2 希尔排序 思路:先取一个正整数d1(d1n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2d1),重复上述分组和排序操作,直到取di=1(=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,…….,di=1 2.3 快速排序:(递归和非递归) 思路:以第一个关键字K1为控制字,将[K1、K2、….Kn]分成两个子区,使左区的有关键字小于等于K1,右区所有关键字大于等于K1,最后控制居两个子区中间的适当位置。在子区内数据尚处于无序状态。将右区首、尾指针保存入栈,对左区进行与第(1)步相类似的处理,又得到它的左子区和右子区,控制字区中。重复第(1)、(2)步,直到左区处理完毕。然后退栈对一个个子区进行相类似的处理,直到栈空。 分区处理函数hoare 思路:首先用两个指针i、j分别指向首、尾两个关键字,i=1,j=8。如对(46、56、14、43、95、10、19、72)。第一个关键字46作为控

文档评论(0)

ze122230743 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档