数据结构实验报告——排序

(此文档为word格式，下载后您可任意编辑修改！)

2008级数据结构实验报告

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

日 期： 2009年12月6日

1．实验要求

a. 实验目的

通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 b. 实验内容

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

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

1 2. 程序分析

2.1 存储结构

存储结构:

顺序存储结构 示意图如下:

2.2 关键算法分析 核心算法思想：

1. 利用教材讲述的基本算法思想，实现七种排序算法，统计其运行相关数据。

2. 将七种排序函数入口地址作为函数指针数组，实现快速调用和统计。使得程序代码可读

性增、结构更加优化。 关键算法思想描述和实现： 关键算法1：

实现七种算法的基本排序功能。

1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

2、希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

3、冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。

2 4、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。

5、选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。

6、堆排序：通过建立大根堆或者小根堆，取出根节点，反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。

7、归并排序：将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。

C++实现：

参看源代码的七个排序函数。

关键算法2：

获取当前系统时间，精确到微秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。此处调用函数QueryPerformanceCounter()用于得到高精度计时器的值。 C++实现：

long double Sort::GetNowTime(void) {

LARGE_INTEGER litmp; LONG64 QPart;

QueryPerformanceCounter(&litmp); }

QPart=litmp.QuadPart; return (long double)QPart;

关键算法3：

3 试图寻求最简短的代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计、算法时间的精确而简易的统计、算法移动次数和比较次数的精确统计。如果设计不合理，将使得主调函数的调用代码冗长，可读性变差。

采用以下三种方法实现：

① 使用函数指针数组，分别指向各排序函数的入口地址，然后在Statistics()函数中加

以调用，使得排序函数运行在统计时间函数之间，这样使用一个for语句即可实现七种算法的一次性调用、时间统计、移动次数和比较次数统计。 C++实现：

void Statistics(Sort &obj,int i,int j) {

obj.startTime=obj.GetNowTime(); (obj.*pFunction[i])(obj.pRandom1); obj.endTime=obj.GetNowTime();

obj.runtime[i][j]=obj.endTime-obj.startTime; }

② 使用两个数组实现乱序、顺序以及逆序数据的排序，大大节省了空间的消耗。基本

思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。 C++实现： 请参看源代码。

③ 建立两个数组分别统计运行次数，再统一使用一个数组记录七种算法在三种不同数

4 据情况下的移动次数和交换次数。在分别运行乱序、顺序和逆序数组排序时取出前两个数组的值写入第三个数组，然后置零继续统计。 C++实现： 请参看源代码。

时间复杂度与空间复杂度：

理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示：

排序方法 直接插入排序 希尔排序 起泡排序 快速排序 简单选择排序 堆排序 归并排序

平均情况 O(n2) 最好情况 O(n) O(n1.3) 最坏情况 O(n2) O(n2) O(n2) O(n2) O(n2) 辅助空间 O(1) O(nlog2n)~O(n2) O(n2) O(1) O (n) O(1) O(nlog2n) O(n2) O(nlog2n) O(n2) O(log2n) ~O(n) O(1) O(nlog2n) O(nlog2n) O (nlog2n) O(1) O(nlog2n) O(nlog2n) O(nlog2n) O(n) 5