数据结构实验报告

实验名称： 实验四——排序 学生姓名： 班级： 班内序号： 学号：

日 期： 2013年12月16日

1． 实验要求

使用简单数组实现下面各种排序算法，并进行比较。 排序算法：

1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试线性表的正确性。

2. 程序分析

2.1 存储结构

使用最简单的一维数组存储待排序的数据。共使用三个数组，一个用来构造正序数组，一个

是逆序数组，还有一个是随机数组。每种排序使用的数组都是具有相同初始值的，因而使得试验结果具有可比较性。

2.2关键算法分析

2.2.1 插入排序算法

插入排序的思想是：每次从无序区取一元素将其添加到有序区中。

2.2.2 希尔排序算法

希尔排序是一种缩小增量排序的算法，首先将待排序元素集按照一定间隔分成多个子集，分别对这些子集进行直接插入排序，整个序列部分有序。然后缩小间隔，在进行直接插入排序，直到间隔为1，此时，整个序列已全部有序。

2.2.3 起泡排序

起泡排序的思想是：两两比较相邻的元素，如果反序，则交换次序，直到没有反序的元素为止。

在此思想指导下①首先将待排序元素划分为有序区和无序区，初始状态有序区为空，无序区所有待排序素；

②对无序区从前向后依次将相邻元素关键码进行比较，若反序，则交换 ③重复执行

②直到无序区中没有元素。

2.2.4快速排序算法

2,2,4,1一趟快速排序算法自然语言描述如下 ① 选取区间第一个元素作为轴值

② 读取区间首尾坐标，并将其左右侧待比较元素

③ 右侧扫描：从后向前找到第一个比轴值小的元素，和左侧待比较元素交换（左侧第一个带比较元素为轴值）

④ 左侧扫描：从前向后找到第一个比轴值大的元素，和右侧待比较元素交换 ⑤ 重复②③，直到左右两侧带比较元素的坐标相等 其c++描述如下

2.2.4.2完整的快速排序算法如下：

2.2.5选择排序算法

选择排序自然语言描述如下：

① 在r[1]~r[n]待排序元素序列中选出最小记录，将其与第一个元素r[n]交换 ② 在r[2]~r[n]待排序元素序列中选出最小记录，将其与第一个元素r[i]交换 …………

③ 直至r[n-1]~r[n] C++描述如下：