南邮数据结构上机实验四内排序算法的实现以及性能比较介绍.pdf

实验报告

（2015/2016学年第二学期）

课程名称数据结构A

实验名称内排序算法的实现以及性能比较

实验时间2016年5月26日

指导单位计算机科学与技术系

指导教师骆健

学生姓名耿宙班级学号

学院(系)管理学院专业信息管理与信息系统

1/17

实习题名:内排序算法的实现及性能比较

班级B141116姓名耿宙学号日期2016.05.26

一、问题描述

验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速

排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生

大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行

比较。系统时钟包含在头文件“time.h”中。

二、概要设计

文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，

冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快

速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示：

三、详细设计

1.类和类的层次设计

在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机

生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函

数main的流程图：

2/17

3/17

main()

2.核心算法

1)简单选择排序：

简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与

r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，

第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到

4/17

全部排序完毕。

2)直接插入排序：

插入排序的思想是将一组无序的元素分别插入一个已经有序的的数组里，并保证插入后的数组

也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组n[1…r]为初

始的一个无序数组（为了直观起见，我们这里设定数组从1开始，而不是0），则n[1]默认为

只有一个元素的有序数组，n[2]插入只有n[1]构成的有序数组中，则此时有序数组的元素数量

变为2。以此类推，到第i个元素时，前i-1个元素已经是有序的，此时只需将第i个元素插

入到有序数组中并使之保持有序。如此直至最后一个元素插入完毕，整个插入排序完成。

3)冒泡排序：

冒泡排序每遍历一次数组，便将最大的元素放到数组最后边。下次遍历将次大的元素放到数组

倒数第二位，依次类推，直至将最小的元素放到最前边，此时冒泡排序完成。

4)快速排序：

快速排序是采用了分而治之的思想，但与合并排序有所不同的是快速排序先“工作”（这里是

分割或partition），再递归。快速排序的主要思想是保证数组前半部分小于后半部分的元素，

然后分别对前半部分和后半部分再分别进行排序，直至所有元素有序