实 验 报 告（ 2015 / 2016 学年 第二学期）课程名称数据结构 A 实验名称内排序算法的实现以及性能比较实验时间2016 年5 月26 日指导单位计算机科学与技术系指导教师骆健学生姓名耿宙班级学号B14111615 学院 (系) 管理学院专业信息管理与信息系统实习题名 : 内排序算法的实现及性能比较班级 B141116 姓名耿宙学号 B14111615 日期 2016.05.26 一、问题描述验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10 个元素师改用直接插入排序；使用随即数发生器产生大数据集合， 运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h ”中。二、概要设计文件 Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序 BubbleSort()，两路合并排序Merge() ，快速排序 QuickSort()以及改进的快速排序 GQuickSort()六个内排序算法函数。主主函数main 的代码如下图所示：三、详细设计1.类和类的层次设计在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函数 main 的流程图：main() 2.核心算法1)简单选择排序：简单选择排序的基本思想是：第1 趟，在待排序记录r[1]~r[n] 中选出最小的记录，将它与r[1] 交换；第 2 趟，在待排序记录r[2]~r[n] 中选出最小的记录，将它与r[2] 交换；以此类推，第 i 趟在待排序记录r[i]~r[n] 中选出最小的记录，将它与 r[i]交换，使有序序列不断增长直到全部排序完毕。2)直接插入排序：插入排序的思想是将一组无序的元素分别插入一个已经有序的的数组里，并保证插入后的数组也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组n[1 ⋯r] 为初始的一个无序数组（为了直观起见，我们这里设定数组从1 开始，而不是0），则 n[1] 默认为只有一个元素的有序数组，n[2] 插入只有n[1] 构成的有序数组中，则此时有序数组的元素数量变为 2。以此类推，到第i 个元素时，前i-1个元素已经是有序的，此时只需将第i 个元素插入到有序数组中并使之保持有序。如此直至最后一个元素插入完毕，整个插入排序完成。3)冒泡排序：冒泡排序每遍历一次数组，便将最大的元素放到数组最后边。下次遍历将次大的元素放到数组倒数第二...
VIP
