南邮数据结构上机实验四内排序算法的实现以及性能比较VIP专享

实 验 报 告( 2 ０１５ / 2025 学年 第二学期)课程名称数据结构Ａ实验名称内排序算法得实现以及性能比较实验时间201 ６年５月26日指导单位计算机科学与技术系指导老师骆健学生姓名耿宙班级学号Ｂ１ 411 １ 61 ５学院(系） 管理学院专 业信息管理与信息系统 实习题名:内排序算法得实现及性能比较班级 B １ 4 １ 116 姓名 耿宙 学号 B14111 ６ 1 ５ 日期20 １ 6 、 05 、 26 一、问题描述验证教材得各种内排序算法,分析各种排序算法得时间复杂度;改进教材中得快速排序算法,使得当子集合小于 10 个元素师改用直接插入排序；使用随即数发生器产生大数据集合,运行上述各排序算法,使用系统时钟测量各算法所需得实际时间，并进行比较。系统时钟包含在头文件“time、h”中.二、概要设计文件 Sort、c ｐ p 中包括了简单选择排序 Se ｌ e ｃ tS ｏ rt(）,直接插入排序InsertS ｏ r ｔ(）,冒泡排序 B ｕ bbl ｅ Sort（），两路合并排序 M ｅｒ ge()，快速排序 Quick Ｓ ort()以及改进得快速排序 G Ｑ uickSo ｒｔ（）六个内排序算法函数。主主函数ｍ a ｉ n 得代码如下图所示:三、详细设计1. 类与类得层次设计在此次程序得设计中没有进行类得定义。程序得主要设计就是使用各种内排序算法对随机生成得数列进行排列,并进行性能得比较，除此之外还对快速排序进行了改进。下图为主函数 m ａ i ｎ得流程图：main（）2. 核心算法1)简单选择排序:简单选择排序得基本思想就是：第 1 趟，在待排序记录 r[1]～r[ｎ]中选出最小得记录，将它与 r[1]交换；第２趟，在待排序记录ｒ［2]～r[n]中选出最小得记录，将它与 r[2］交换;以此类推,第 i 趟在待排序记录 r[ｉ]~r[n］中选出最小得记录，将它与 r[i］交换,使有序序列不断增长直到全部排序完毕.2)直接插入排序:插入排序得思想就是将一组无序得元素分别插入一个已经有序得得数组里,并保证插入后得数组也就是有序得。当所有无序组得元素都插入完毕时,一个有序数组构造完成。数组 n［１…ｒ]为初始得一个无序数组(为了直观起见,我们这里设定数组从１开始，而不就是０),则n[1］默认为只有一个元素得有序数组，ｎ［2]插入只有 n[１］构成得有序数组中,则此时有序数组得元素数量变为 2。以此类推,到第 i 个元素时,前 i-1 个元素已经就是有序得，此时只需将第 i 个元素插入到有序数组中并使之保持有序．如此直至最后一个元素插...