各种排序算法时间性能的比较.doc

天津城市建设学院 课程设计任务书 2011 —2012 学年第一学期 电子与信息工程 系 专业 班级 课程设计名称： 数据结构课程设计 设计题目： 各种排序算法时间性能的比较 完成期限：自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周 设计依据、要求及主要内容（可另加附页）： 一、设计依据 [1]《数据结构课程设计指导书》 [2]《数据结构课程设计大纲》 二、设计要求 通过这次设计，要求在数据结构的逻辑特性和物理表示，数据结构的选择的应用、算法的设计及其实现等方面中深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 三、设计内容 1) 问题描述 对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。 2) 基本要求 (1) 设计并实现上述各种排序算法； (2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能； (3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。 3) 设计思想 上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。 直接插入排序、起泡排序、直接选择排序在教材中已经实现，请仿照教材中的方法在其他排序算法中的适当位置插入计数器统计元素的比较次数和移动次数。 【思考题】如果测算每种排序算法所用实际的时间，应如何修改排序算法？ 四、参考资料 [1] 王红梅. 数据结构 C++.北京：清华大学出版社，2005. [2] 王红梅. 数据结构C++实验指导书.北京：清华大学出版社，2005. [3] 严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日  目录 一、需求分析 5 1) 需求描述 5 2) 要求 5 3) 设计思想 5 二、总体设计 5 1）程序的系统构造 5 2）程序的函数构造及其实现方式 6 三、详细设计 6 1）数组的录入及其生成 6 2）排序算法 7 3）记录排序过程 9 4）分析并输出结果 9 四、调试与测试 10 五、关键源程序清单和执行结果 13 1）快速排序和堆排序源程序 13 2）执行结果概览 14 六、参考文献 15 一、需求分析 各种排序算法时间性能的比较 1) 需求描述 对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。 2) 要求 (1) 设计并实现上述各种排序算法； (2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能； (3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。 3) 设计思想 上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。 二、总体设计 1）程序的系统构造 时间分析是附加功能，时间分析比步数分析更能精确的记录程序的运行过程。 2）程序的函数构造及其实现方式 (1)程序存储结构 所有输入均使用顺序表存储结构。在二叉树的操作中，用 n*2 计算左孩子节点， n*2-1 计算右孩子节点；同理，使用 n/2 计算孩子的父节点。 数组的赋值操作是使用循环对其各项一一赋值。 (2)排序，记录步数 对同一个数组一次进行直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序，统计各个算法中的比较次数和移动次数。 (3)分析结果 对各个算法运行后记录下的总步数进行排序，比较出效率最好的算法和最差第算法。 三、详细设计 1）数组的录入及其生成 生成数组后，用循环对数组进行赋值，代码如下： void initYours( int *test,int n) { for( int i = 0; i n; i++) { cin test[ i]; } } 在数组的赋值过程中，必须传入数组长度。然后从test[0..n]依次对数组进行赋值。 在随机