2008级数据结构实验报告

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

实验要求

a. 实验目的

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

2 题目2

使用链表实现下面各种排序算法，并进行比较。 排序算法：

1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他

要求：

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

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

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

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

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

2.程序分析：

1.存储结构：单链表

S1 S2 S3

front 结点结构体为： struct Node｛ int data； Node * next｝ data Node* next 2. 核心算法思想：

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

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

增、结构更加优化。 3. 关键算法的实现： 关键算法1：

实现四种算法的基本排序功能。 1、

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

具体实现为：每次将s赋值为头结点，而p最初赋值为第一个含有data的指针。每次比较p和s的后继的数据大小，若是p的数据小于s的数据则将p的后继结点插入到s结点的后面同时s返回到头结点重新比较插入，直至p到达链表的尾部。 void LinkSort::InsertSort()

//插入排序

{Node * P = front->next; while(P->next) {Node * S = front;

while(1)

{ CompareCount++;

//要插入的节点的前驱

//用来比较的节点的前驱

if( P->next->data < S->next->data ) // P后继比S后继小则把p的后继结

点插入到s后继结点的后面，同时跳出这一层循环，将s重新赋值为front结点指针。

{ insert(P, S); break; }

S = S->next; //若p的后继不比s后继小，则将s指针后移，继续比较。

if(S==P)

{ P = P->next; break; }//若是s和p成为同一个指针，则将p指针后移，将进行下一

次比较。

}} }

2、冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。 本代码使用链表结构，并且用改良版的冒泡排序。每次用指针pos记录排序进行的最后位置，即为尾部正序链表的首个结点，从而实现了算法的简洁，节省了时间。 void LinkSort::BubbleSort()

{Node * P = front->next;//p是front结点的后继 while(P->next)

//第一趟排序并查找无序范围

{CompareCount++;

if( P->data > P->next->data)//如果p的data比其后继的data大，则将两者的data交换

swap(P, P->next);

}

P = P->next;

Node * pos = P; P = front->next;//用指针pos记录比较的最后位置 while(pos != front->next) { } }

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

由于使用链表结构，使用递归函数进行递归调用，每次将原链表再分成两个小的链表，将排序函数递归调用实现快速排序。而单链表每个节点只能记录其后一个结点，故而每次轴结点都为递归函数节点参量的头结点。

Node * bound = pos; pos = front->next; while(P->next != bound) { }

P = front->next;

CompareCount++; if( P->data > P->next->data) { swap(P, P->next); pos = P->next;} P = P->next;