14-排序算法性能分析.doc

计算机科学与技术本科专业
数据结构课程设计任务书

题目：排序算法性能分析
学生姓名：学号：班级：
题目类型：软件工程（R）指导教师：张其文

题目简介
排序是计算机程序设计中的一种重要操作。各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。该设计要求学生演掌握各种排序的基本思想及排序算法。通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。

主要任务
第一部分：基本算法实现
线性结构基本算法实现（指导老师根据题目指定）；
树型结构基本算法实现（指导老师根据题目指定）；
图型结构基本算法实现（指导老师根据题目指定）；
查找基本算法实现（指导老师根据题目指定）；
排序基本算法实现（指导老师根据题目指定）；
第二部分：指定题目的设计与实现
1、查阅文献资料，一般在3篇以上；
2、建立排序数据的逻辑结构和物理结构；
3、完成相应算法的设计；
4、完成测试工作；
5、撰写设计说明书；
6、做好答辩工作。

主要内容、功能及技术指标
（1）使用连续的存储单元存放待排序记录，实现插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等功能，并对排序性能进行分析；
（2）利用随机函数产生2000个随机整数、正序、逆序数据作为测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；
（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；
（4）较高要求：能够用动画演示相应的排序过程。

提交的成果
1.设计说明书一份，内容包括：
1)中文摘要100字；关键词3-5个；
2)序言；
3）采用类c语言定义相关的数据类型
4）各模块流程图及伪码算法
5）函数的调用关系图
6）调试分析
a、调试中遇到的问题及对问题的解决方法；
b、算法的时间复杂度和空间复杂度。
7）测试结果
8）源程序（带注释）
9)设计总结、参考文献、致谢等。
2.刻制光盘一张。

主要参考文献
1严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.
2严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.
3《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学出版社（影印版）.
4谭浩强.《c语言程序设计》.清华大学出版社.
5．数据结构与算法分析（Java版）,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionHYPERLINK"http://www.china-pub.com/search/power_search/power_search.asp?key1=Clifford+A.+Shaffer"\t"_parent"CliffordA.Shaffer,张铭,刘晓丹译电子工业出版社2001年1月

2012年5月18日