发布时间 : 星期日 文章南邮数据结构上机实验四内排序算法的实现以及性能比较更新完毕开始阅读9883f069f9c75fbfc77da26925c52cc58ad69076
.
实 验 报 告
（ 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]交换，使有序序
.