实验四排序实验报告.docx
- 文档编号:15012186
- 上传时间:2023-06-29
- 格式:DOCX
- 页数:16
- 大小:100.78KB
实验四排序实验报告.docx
《实验四排序实验报告.docx》由会员分享,可在线阅读,更多相关《实验四排序实验报告.docx(16页珍藏版)》请在冰点文库上搜索。
实验四排序实验报告
数据结构实验报告
实验名称:
实验四排序
学生姓名:
班级:
班内序号:
学号:
日期:
2012年12月21日
1、实验要求
题目2
使用链表实现下面各种排序算法,并进行比较。
排序算法:
1、插入排序
2、冒泡排序
3、快速排序
4、简单选择排序
5、其他
要求:
1、测试数据分成三类:
正序、逆序、随机数据。
2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。
3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)。
4、对2和3的结果进行分析,验证上述各种算法的时间复杂度。
编写测试main()函数测试线性表的正确性。
2、程序分析
2.1存储结构
说明:
本程序排序序列的存储由链表来完成。
其存储结构如下图所示。
(1)单链表存储结构:
A[2]
1080H
……
A[0]
10C0H
……
A[3]
NULL
……
A[1]
1000H
……
(2)结点结构
structNode
{
intdata;
Node*next;
};
示意图:
2.2关键算法分析
一:
关键算法
(一)直接插入排序voidLinkSort:
:
InsertSort()
直接插入排序是插入排序中最简单的排序方法,其基本思想是:
依次将待排序序列中的每一个记录插入到一个已排好的序列中,直到全部记录都排好序。
(1)算法自然语言
1.将整个待排序的记录序列划分成有序区和无序区,初始时有序区为待排序记录序列中的第一个记录,无序区包括所有剩余待排序的记录;
2.将无须去的第一个记录插入到有序区的合适位置中,从而使无序区减少一个记录,有序区增加一个记录;
3.重复执行2,直到无序区中没有记录为止。
(2)源代码
voidLinkSort:
:
InsertSort()//从第二个元素开始,寻找前面那个比它大的
{
Node*P=front->next;//要插入的节点的前驱
while(P->next)
{
Node*S=front;//用来比较的节点的前驱
while
(1)
{
CompareCount++;
if(P->next->data
{
insert(P,S);
break;
}
S=S->next;
if(S==P)//若一趟比较结束,且不需要插入
{
P=P->next;
break;}
}
}
}
(3)时间和空间复杂度
最好情况下,待排序序列为正序,时间复杂度为O(n)。
最坏情况下,待排序序列为逆序,时间复杂度为O(n2)。
直接插入排序只需要一个记录的辅助空间,用来作为待插入记录的暂存单元和查找记录的插入位置过程中的“哨兵”。
直接插入排序是一种稳定的排序方法。
直接插入排序算法简单容易实现,当序列中的记录基本有序或带排序记录较少时,他是最佳的排序方法。
但当待排序的记录个数较多时,大量的比较和移动操作使直接插入排序算法的效率减低。
直接插入排序过程
初始键值序列[12]1592063124
第一趟排序结果[1215]92063124
第二趟排序结果[91215]2063124
第三趟排序结果[9121520]63124
第四趟排序结果[69121520]3124
第五趟排序结果[6912152031]24
第六趟排序结果[691215202431]
(二)冒泡排序voidLinkSort:
:
BubbleSort()
冒泡排序是交换排序中最简单的排序方法,其基本思想是:
两两比较相邻记录的关键码,如果反序则交换,直到没有反序的记录为止。
本程序采用改进的冒泡程序。
(1)算法自然语言
1.将整个待排序的记录序列划分成有序区和无序区,初始状态有序区为空,无序区包括所有待排序的记录。
2.对无序区从前向后依次将相邻记录的关键码进行比较,若反序则交换,从而使得关键码小的记录向前移,关键码大的记录向后移(像水中的气泡,体积大的先浮上来)。
3.将最后一次交换的位置pos,做为下一趟无序区的末尾。
4.重复执行2和3,直到无序区中没有反序的记录。
(2)源代码
voidLinkSort:
:
BubbleSort()
{
Node*P=front->next;
while(P->next)//第一趟排序并查找无序范围
{
CompareCount++;
if(P->data>P->next->data)
swap(P,P->next);
P=P->next;
}
Node*pos=P;
P=front->next;
while(pos!
=front->next)
{
Node*bound=pos;
pos=front->next;
while(P->next!
=bound)
{
CompareCount++;
if(P->data>P->next->data)
{
swap(P,P->next);
pos=P->next;
}
P=P->next;
}
P=front->next;
}
}
(3)时间和空间复杂度
在最好情况下,待排序记录序列为正序,算法只执行了一趟,进行了n-1次关键码的比较,不需要移动记录,时间复杂度为O(n);
在最坏情况下,待排序记录序列为反序,时间复杂度为O(n2),空间复杂度为O
(1)。
冒泡排序是一种稳定的排序方法。
(三)快速排序voidLinkSort:
:
Qsort()
(1)算法自然语言
1.首先选一个轴值(即比较的基准),将待排序记录分割成独立的两部分,左侧记录的关键码均小于或等于轴值,右侧记录的关键码均大于或等于轴值。
2.然后分别对这两部分重复上述过程,直到整个序列有序。
3.整个快速排序的过程递归进行。
(2)源代码
voidLinkSort:
:
Qsort()
{
Node*End=front;
while(End->next)
{
End=End->next;
}
Partion(front,End);
}
voidLinkSort:
:
Partion(Node*Start,Node*End)
{
if(Start->next==End||Start==End)//递归返回
return;
Node*Mid=Start;//基准值前驱
Node*P=Mid->next;
while(P!
=End&&P!
=End->next)
{
CompareCount++;
if(Mid->next->data>P->next->data)//元素值小于轴点值,则将该元素插在轴点之前
{
if(P->next==End)//若该元素为End,则将其前驱设为End
End=P;
insert(P,Mid);
Mid=Mid->next;
}
elseP=P->next;
}
Partion(Start,Mid);//递归处理基准值左侧链表
Partion(Mid->next,End);//递归处理基准值右侧链表
}
(3)时间和空间复杂度
在最好的情况下,时间复杂度为O(nlog2n)。
在最坏的情况下,时间复杂度为O(n2)。
快速排序是一种不稳定的排序方法。
(四)简单选择排序
基本思想为:
第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->next->next)
{
Node*P=S;
Node*Min=P;
while(P->next)//查找最小记录的位置
{
CompareCount++;
if(P->next->data
Min=P;
P=P->next;
}
insert(Min,S);
S=S->next;
}
}
(3)时间和空间复杂度
简单选择排序最好、最坏和平均的时间复杂度为O(n2)。
简单选择排序是一种不稳定的排序方法。
(五)输出比较结果函数(含计算函数体执行时间代码)
(1)算法自然语言
1、依次调用直接插入排序、冒泡排序、快速排序、简单选择排序的函数体,进行序列的排序,并输出相应的比较次数、移动次数。
2、获取当前系统时间。
在调用函数之前设定一个调用代码前的时间,在调用函数之后再次设定一个调用代码后的时间,两个时间相减就是代码运行时间。
说明:
运用QueryPerformanceFrequency()可获取计时器频率;QueryPerformanceCounter()用于得到高精度计时器的值。
(2)源代码
voidprintResult(LinkSort&a,LinkSort&b,LinkSort&c,LinkSort&d)
{
_LARGE_INTEGERtime_start;//开始时间
_LARGE_INTEGERtime_over;//结束时间
doubledqFreq;//计时器频率
LARGE_INTEGERf;//计时器频率
QueryPerformanceFrequency(&f);
dqFreq=(double)f.QuadPart;
a.print();
doubleTimeCount;
CompareCount=0;MoveCount=0;TimeCount=0;
QueryPerformanceCounter(&time_start);//记录起始时间
a.InsertSort();
QueryPerformanceCounter(&time_over);//记录结束时间
TimeCount=((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;
cout<<"排序结果:
";a.print();
cout<<"1.插入。
比较次数:
"< "< "< CompareCount=0;MoveCount=0;TimeCount=0; QueryPerformanceCounter(&time_start);//记录起始时间 b.BubbleSort(); QueryPerformanceCounter(&time_over);//记录结束时间 TimeCount=((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; cout<<"2.冒泡。 比较次数: "< "< "< CompareCount=0;MoveCount=0;TimeCount=0; QueryPerformanceCounter(&time_start);//记录起始时间 c.Qsort(); QueryPerformanceCounter(&time_over);//记录结束时间 TimeCount=((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; cout<<"3.快速。 比较次数: "< "< "< CompareCount=0;MoveCount=0;TimeCount=0; QueryPerformanceCounter(&time_start);//记录起始时间 d.SelectSort(); QueryPerformanceCounter(&time_over);//记录结束时间 TimeCount=((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; 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++编程语言,必须要加强这方面的训练,这样才能在将编程思想和数据结构转换为代码的时候能得心应手。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 排序 报告