数据结构实验报告
实验名称：实验四 排序 学生姓名： 班级： 班内序号： 学号：
日期：2012年12月21日 1、 实验要求
题目2
使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求：
1、测试数据分成三类：正序、逆序、随机数据。
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）。
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。 编写测试main()函数测试线性表的正确性。
2、 程序分析
存储结构
说明：本程序排序序列的存储由链表来完成。 其存储结构如下图所示。 (1)单链表存储结构：
A[2] 1080H …… A[0] 10C0H …… A[3] NULL …… A[1] 1000H ……
（2）结点结构
地址：1080H 地址：1020H 头指针 结点 地址：1000H 地址：10C0H struct Node {
int data;
Node * next; };
示意图： int data
Node * next 关键算法分析
一：关键算法
(一)直接插入排序 void LinkSort::InsertSort()
直接插入排序是插入排序中最简单的排序方法，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好序。 （1）算法自然语言
1.将整个待排序的记录序列划分成有序区和无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有剩余待排序的记录；
2.将无须去的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录；
3.重复执行2，直到无序区中没有记录为止。
（2）源代码
void LinkSort::InsertSort() 整个待排序的记录序列插入到合适位置 初始键值序列 ［12］ 15 9 20 6 31 24 划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。 r1≤r2≤ … … ≤ri-1 ri ri+1 … … rn 第一趟排序结果 ［12 15］ 9 20 6 31 24 2.对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得关键码小 的记录向前移，关键码大的记录向后移（像水中的气泡，体积大的先浮上来）。 第二趟排序结果 ［9 12 15］ 20 6 31 24 有序区 无序区 3.将最后一次交换的位置pos，做为下一趟无序区的末尾。 第三趟排序结果 ［9 12 15 20］ 6 31 24 4.重复执行2和3，直到无序区中没有反序的记录。
第四趟排序结果 ［6 9 12 15 20］ 31 24 直接插入排序过程
实验四-排序-实验报告
