排序的实验报告范文.docx
《排序的实验报告范文.docx》由会员分享，可在线阅读，更多相关《排序的实验报告范文.docx（15页珍藏版）》请在冰点文库上搜索。
排序的实验报告范文
排序的实验报告范文
数据结构实验报告
实验名称：
实验四排序
学生姓名：
班级：
班内序号：
学号：
日期：
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
第四趟排序结果132********56597
冒泡排序过程
（三）快速排序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（）
{
Node某S=front;
while（S->ne某t->ne某t）
{
Node某P=S;
Node某Min=P;
while（P->ne某t）//查找最小记录的位置
{
if（P->ne某t->datane某t->data）
Min=P;
P=P->ne某t;
}
inert（Min,S）;
S=S->ne某t;
}
}
（3）时间和空间复杂度
简单选择排序最好、最坏和平均的时间复杂度为O（n2）。
简单选择排序是一种不稳定的排序方法。
初始键值序列
初始键值序列［49276597761338］
第一趟排序结果13［276597764938］
第二趟排序结果1327［6597764938］
第三趟排序结果132738［97764965］
第四趟排序结果13273849［769765］
第五趟排序结果1327384965［9776］
第六趟排序结果132********697
简单选择排序的过程示例
（五）输出比较结果函数（含计算函数体执行时间代码）
（1）算法自然语言
1、依次调用直接插入排序、冒泡排序、快速排序、简单选择排序的函数体，进行序列的排序，并输出相应的比较次数、移动次数。
2、获取当前系统时间。
在调用函数之前设定一个调用代码前的时间，在调用函数之后再次设定一个调用代码后的时间，两个时间相减就是代码运行时间。
说明：
运用QueryPerformanceFrequency（）可获取计时器频率；QueryPerformanceCounter（）用于得到高精度计时器的值。
（2）源代码
voidprintReult（LinkSort&a,LinkSort&b,LinkSort&c,LinkSort&d）
{
doubledqFreq;//计时器频率
LARGE_INTEGERf;//计时器频率
QueryPerformanceFrequency（&f）;
dqFreq=（double）f.QuadPart;
a.print（）;
doubleTimeCount;
a.InertSort（）;
cout<<"排序结果：
";a.print（）;
cout<<"1.插入。
b.BubbleSort（）;
cout<<"2.冒泡。
c.Qort（）;
cout<<"3.快速。
d.SelectSort（）;
cout<<"4.选择。
}
（3）时间和空间复杂度
时间复杂度O
（1）（因为不包含循环体）。
2.3其他
排序方法
平均情况
最好情况
最坏情况
辅助空间
直接插入排序
O（n2）
O（n）
O（n2）
O
（1）
希尔排序
O（nlog2n）~O（n2）
O（n1.3）
O（n2）
O
（1）
起泡排序
O（n2）
O（n）
O（n2）
O
（1）
快速排序
O（nlog2n）
O（nlog2n）
O（n2）
O（log2n）~O（n）
简单选择排序
O（n2）
O（n2）
O（n2）
O
（1）
堆排序
O（nlog2n）
O（nlog2n）
O（nlog2n）
O
（1）
归并排序
O（nlog2n）
O（nlog2n）
O（nlog2n）
O（n）
3、程序运行结果
（1）程序流程图
开始
开始
输入数据
输入数据
顺序数组四种排序和统计
顺序数组四种排序和统计
逆序数组四种排序和统计
逆序数组四种排序和统计
乱序数组四种排序和统计
乱序数组四种排序和统计
输出统计结果
输出统计结果
结束
结束
（2）测试条件
规模为10个数字，在正序、逆序和乱序的条件下进行测试，未出现问题。
（3）运行结果：
（4）说明：
各函数运行正常，没有出现bug。
四、总结
1、调试时出现的问题及解决方法
由于经过一种排序后，原始数据改变，导致后面的排序所用的数据全为排好后的数据。
将数据在排序前重新初始化后，该问题被排除。
还有就是因为编程时没有注意格式，所以在调试错误时花费了不少时间。
2、心得体会
这是最后一次编程实验。
这次试验，我觉得主要目的还是在掌握好课本知识的基础上，对代码进行相应的优化，以达到时间复杂度和空间复杂度的最佳。
其次，本次实验是经过借鉴课本上的程序进行编写，是基于课本完成的。
考虑到若完全由自己编写，则又可能限于自己能力问题，将较简单的算法编写的过于麻烦，造成关键码的比较次数和移动次数比一些复杂算法还多，从而影响结果。
基于课本编写，最大好处是可以借鉴、仔细研读书上的优秀例子，开拓以后编写程序的思路。
基于课本编写，最大坏处是自己独立思考、独立编写、修改程序的能力未得到锻炼。
对于正序序列，直接插入、起泡排序法有较高的效率。
对于逆序序列，简单选择排序效率较高。
对于在随机序列，快速排序法的效率比较高。
程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。
这次做优化的过程中，遇到不少阻力。
由于优化中用到很多类的封装和访问控制方面的知识，而这部分知识恰好是大一一年学习的薄弱点。
因而以后要多花力气学习C++编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。
升级会员 