各种排序算法课程设计报告

《各种排序算法课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、封面本科学生课程设计任务书课程设计题目内部排序算法比较学院软件学院专业软件工程年级2008级已知参数和设计要求：[问题描述]各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。学生应完成的工作：[基本要求]（1）对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。（2）待排序表的表长不少于100；其中的数据

2、要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。[测试数据]由随机产生器决定。目前资料收集情况（含指定参考资料）：《C++数据结构与程序设计》RobertL.KruseAlexanderJ.Ryba北京，清华大学出版社，2004.1课程设计的工作计划：先制作规划大纲，在从基础的表开始做，再研究核心的算法，各种排序函数的实现，最后用其他辅助类用于实现效率的比较，和测试数据的产生。最后在优化程序，添加注释。任务下达日期20

3、10年4月26日完成日期2010年5月30日指导教师（签名）学生（签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003重庆大学本科学生课程设计任务书课程设计题目学院专业年级已知参数和设计要求：学生应完成的工作：目前资料收集情况（含指定参考资料）：课程设计的工作计划：任务下达日期年月日完成日期年月日指导教师（签名）学生（签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。重庆大学本

4、科学生课程设计任务书课程设计题目学院专业年级已知参数和设计要求：学生应完成的工作：目前资料收集情况（含指定参考资料）：课程设计的工作计划：任务下达日期年月日完成日期年月日指导教师（签名）学生（签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。重庆大学本科学生课程设计任务书课程设计题目学院专业年级已知参数和设计要求：学生应完成的工作：目前资料收集情况（含指定参考资料）：课程设计的工作计划：任务下达日期年月

5、日完成日期年月日指导教师（签名）学生（签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。数据结构与算法课程设计摘要本文主要针对各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受，对各种算法比较次数和移动次数的比较，针对各种不同数组如何选择更高效的排序方法，给出一定的指导。各种算法的稳定性也至关重要，对于

6、各种不同类型的数据，各种算法的效果有明显差异，所以针对每种算法，都有不同的数据与之对应，该稳定性表明算法的稳定程度。有效时间则为各种算法针对每组数据实际用掉的计算机时间，可以分析各种排序算法的时间效率。关键字时间复杂度有效时间稳定性数据结构与算法课程设计一问题重述1.1问题描述各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。1.2基本要求（1）对以下10种常用的内部排序算法进行比较：直接插入排序；折半折

7、入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。（2）待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。二算法构建2.1算法思想所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。当待排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同

8、关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。2.1.1插入排序插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入