排序的实验报告范文
- 格式：docx
- 大小：41.84 KB
- 文档页数：20
排序的实验报告范文
数据结构实验报告
实验名称：实验四排序
学生姓名：
班级：
班内序号：
学号：
日期：2022年12月21日
实验要求
题目2
使用链表实现下面各种排序算法，并进行比较。
排序算法：
1、插入排序
2、冒泡排序
3、快速排序
4、简单选择排序
5、其他
要求：
1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）。
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。
编写测试main()函数测试线性表的正确性。
2、程序分析
2.1存储结构
说明：本程序排序序列的存储由链表来完成。
其存储结构如下图所示。
(1)单链表存储结构：
结点地址：1000HA[2]
结点地址：1000H
1080H
……
头指针地址：1020HA[0]
头指针
地址：1020H
10C0H ……
地址：1080HA[3]
地址：1080H
NULL
……
地址：10C0HA[1]
地址：10C0H
1000H
……
（2）结点结构
tructNode
{
intdata;
Node某ne某t;
};
示意图：
intdataNode某ne某t
intdata
Node某ne某t 2.2关键算法分析
一：关键算法
(一)直接插入排序voidLinkSort::InertSort()
直接插入排序是插入排序中最简单的排序方法，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好序。
（1）算法自然语言
1.将整个待排序的记录序列划分成有序区和无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有剩余待排序的记录；
2.将无须去的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录；
3.重复执行2，直到无序区中没有记录为止。
（2）源代码
voidLinkSort::InertSort()//从第二个元素开始，寻找前面那个比它大的{
Node某P=front->ne某t;//要插入的节点的前驱
while(P->ne某t)
{
Node某S=front;//用来比较的节点的前驱
while(1) {
if(P->ne某t->datane某t->data)//P的后继比S的后继小则插入
{
inert(P,S);
break;
}
S=S->ne某t;
if(S==P)//若一趟比较结束，且不需要插入
{
P=P->ne某t;
break;}
}
}
}
(3)时间和空间复杂度
最好情况下，待排序序列为正序，时间复杂度为O（n）。
最坏情况下，待排序序列为逆序，时间复杂度为O（n2）。 直接插入排序只需要一个记录的辅助空间，用来作为待插入记录的暂存单元和查找记录的插入位置过程中的“哨兵”。
直接插入排序是一种稳定的排序方法。直接插入排序算法简单容易实现，当序列中的记录基本有序或带排序记录较少时，他是最佳的排序方法。但当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率减低。
r
r1≤r2≤……≤ri-1riri+1……rn
有序区无序区
直接插入排序的基本思想
插入到合适位置
直接插入排序过程
直接插入排序过程
初始键值序列［12］1592063124
第一趟排序结果［1215］92063124
第二趟排序结果［91215］2063124
第三趟排序结果［9121520］63124
第四趟排序结果［69121520］3124
第五趟排序结果［6912152031］24
第六趟排序结果［691215202431］
（二）冒泡排序voidLinkSort::BubbleSort() 冒泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。本程序采用改进的冒泡程序。
（1）算法自然语言
1.将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。
2.对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得关键码小的记录向前移，关键码大的记录向后移（像水中的气泡，体积大的先浮上来）。
3.将最后一次交换的位置po，做为下一趟无序区的末尾。
4.重复执行2和3，直到无序区中没有反序的记录。
（2）源代码
voidLinkSort::BubbleSort()
{
Node某P=front->ne某t;
while(P->ne某t)//第一趟排序并查找无序范围
{
if(P->data>P->ne某t->data)
wap(P,P->ne某t);
P=P->ne某t; }
Node某po=P;
P=front->ne某t;
while(po!=front->ne某t)
{
Node某bound=po;
po=front->ne某t;
while(P->ne某t!=bound)
{
if(P->data>P->ne某t->data)
{
wap(P,P->ne某t);
po=P->ne某t;
}
P=P->ne某t;
}
P=front->ne某t;
}
} (3)时间和空间复杂度
在最好情况下，待排序记录序列为正序，算法只执行了一趟，进行了n-1次关键码的比较，不需要移动记录，时间复杂度为O（n）；
在最坏情况下，待排序记录序列为反序，时间复杂度为O（n2），空间复杂度为O(1)。
冒泡排序是一种稳定的排序方法。
r
rjrj+1ri+1≤……≤rn-1≤rn
无序区有序区
1≤j≤i-1已经位于最终位置
起泡排序的基本思想
反序则交换
初始键值序列
初始键值序列［5013559727384965］
第一趟排序结果［13505527384965］97
第二趟排序结果［1350273849］556597
第三趟排序结果［13273849］50556597
第四趟排序结果1327384950556597
冒泡排序过程
（三）快速排序voidLinkSort::Qort() （1）算法自然语言
1.首先选一个轴值（即比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值。
2.然后分别对这两部分重复上述过程，直到整个序列有序。
3.整个快速排序的过程递归进行。
（2）源代码
voidLinkSort::Qort()
{
Node某End=front;
while(End->ne某t)
{
End=End->ne某t;
}
Partion(front,End);
}
voidLinkSort::Partion(Node某Start,Node某End)
{
if(Start->ne某t==End||Start==End)//递归返回 return;
Node某Mid=Start;//基准值前驱
Node某P=Mid->ne某t;
while(P!=End&&P!=End->ne某t)
{
if(Mid->ne某t->data>P->ne某t->data)//元素值小于轴点值，则将该元素插在轴点之前
{
if(P->ne某t==End)//若该元素为End，则将其前驱设为End
End=P;
inert(P,Mid);
Mid=Mid->ne某t;
}
eleP=P->ne某t;
}
Partion(Start,Mid);//递归处理基准值左侧链表
Partion(Mid->ne某t,End);//递归处理基准值右侧链表
}
（3）时间和空间复杂度 在最好的情况下，时间复杂度为O（nlog2n）。
在最坏的情况下，时间复杂度为O（n2）。
快速排序是一种不稳定的排序方法。
[
[r1……ri-1]ri[ri+1……rn]
均≤ri轴值均≥ri
位于最终位置
快速排序的基本思想图解
（四）简单选择排序
基本思想为：第i趟排序通过n-i次关键码的比较，在n-i+1（1≤i≤n-1）各记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。
（1）算法自然语言
1.将整个记录序列划分为有序区和无序区，初始状态有序区为空，无序区含有待排序的所有记录。
2.在无序区中选取关键码最小的记录，将它与无序区中的第一个记录交换，使得有序区扩展了一个记录，而无序区减少了一个记录。
3.不断重复2，直到无序区之剩下一个记录为止。
（2）源代码
voidLinkSort::SelectSort()
