C++排序.docx
- 文档编号:14240193
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:14
- 大小:154.84KB
C++排序.docx
《C++排序.docx》由会员分享,可在线阅读,更多相关《C++排序.docx(14页珍藏版)》请在冰点文库上搜索。
C++排序
数据结构实验报告
实验名称:
实验四——排序
学生姓名:
班级:
班内序号:
学号:
日期:
2012年12月13日
1.实验要求
【实验目的】
通过选择实验内容中的两个题目之一,学习、实现、对比各种排序算法,掌握各种排序算法的优劣,以及各种算法的使用的情况。
【实验内容】
使用链表实现下面各种排序算法,并进行比较。
排序算法:
1、插入排序
2、冒泡排序
3、快速排序
4、简单选择排序
5、其他
要求:
1、测试数据分成三类:
正序、逆序、随机数据
2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。
3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)
4、对2和3的结果进行分析,验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性
2.程序分析
[正文格式要求]见1实验要求中的格式要求
2.1存储结构
存储结构:
单链表
非空单链表:
front
空单链表:
front
2.2关键算法分析
【设计思想】
以直接插入排序为例:
首先将待排序数据建立一个带头结点的单链表。
在单链表中进行直接插入排序的基本思想是:
将单链表划分为有序区和无序区,有序区只包含一个元素节点,依次取无序区中的每一个结点,在有序区中查找待插入结点的插入位置,然后把该结点从单链表中删除,再插入到相应位置。
分析上述排序过程,需设一个工作指针q在无序区中指向待插入的结点,为了查找正确的插入位置,每趟排序前需将工作指针pre和p指向头结点和开始结点,在找到插入位置后,将结点q插在结点pre和p之间。
这相当于在单链表中删除结点q,因此为了保证链表不断开,须在删除结点q之前保留结点q的后继结点的地址。
【复杂度】
(1)建立链表存储数据的算法:
template
LinkList
:
LinkList(Ta[],intn)//尾插法建立单链表
{
front=newNode
r=front;
for(inti=0;i { Node s->data=a[i];//将a[i]写入到新结点的数据域 r->next=s;//将新结点加入到链表中 r=s;//修改尾指针 } r->next=NULL;//终端结点的指针域设为空 move=compare=0; } 该算法的时间复杂度为T(n)=O(n) (2)输出数据的算法: template voidLinkList : PrintList() { Node while(p! =NULL) { cout< p=p->next; } cout< } 该算法的时间复杂度为T(n)=O(n) (3)插入排序算法: template voidLinkList : InsertSort()//升序排列 { LARGE_INTEGERBegainTime; LARGE_INTEGEREndTime; LARGE_INTEGERFrequency; QueryPerformanceFrequency(&Frequency); QueryPerformanceCounter(&BegainTime); Node Node q1=front->next; q2=front->next->next; while(q2! =NULL)//对q2的循环 { p1=front; p2=front->next; s->data=q2->data; while(p2! =q2)//对p2的循环 { compare++; if(q2->data { Node p1->next=q2; q2->next=p2; q1->next=temp; q2=temp; move=move+4; break; } p1=p2; p2=p2->next; move=move+4; } if(p2==q2) { q1=q1->next; q2=q2->next; move=move+2; } } QueryPerformanceCounter(&EndTime); cout<<"运行时间: "<<(double)(EndTime.QuadPart-BegainTime.QuadPart)/Frequency.QuadPart<<"s"< } 该算法的时间复杂度T(n)=O(n2) (4)冒泡排序算法: template voidLinkList : BubbleSort() { LARGE_INTEGERBegainTime; LARGE_INTEGEREndTime; LARGE_INTEGERFrequency; QueryPerformanceFrequency(&Frequency); QueryPerformanceCounter(&BegainTime); Node while(pos! =front) { Node pos=front;move++; Node while(p! =bound) { compare++; if(p->data>p->next->data)//相邻元素比较 { Ttemp=p->data;//交换 p->data=p->next->data; p->next->data=temp; pos=p; move=move+3; } p=p->next;move++; } } QueryPerformanceCounter(&EndTime); cout<<"运行时间: "<<(double)(EndTime.QuadPart-BegainTime.QuadPart)/Frequency.QuadPart<<"s"< } 该算法的时间复杂度T(n)=O(n2) (5)快速排序算法: template voidLinkList : QuickSort(Node { if(first==end) return; Node i=j=first; while(j! =end->next) { compare++; if(j->data { i=i->next; Ttemp=i->data;//交换i和j的值 i->data=j->data; j->data=temp; move=move+4; } j=j->next;move++; } Tt=i->data;//交换first和i的值 i->data=first->data; first->data=t; move=move+3; QuickSort(first,i);//递归排序i的前半部分 if(i->next! =end->next)//防止越界 QuickSort(i->next,end);//递归排序i的后半部分 } 该算法的时间复杂度T(n)=O(nlogn) (6)简单选择排序算法: template voidLinkList : SelectSort() { LARGE_INTEGERBegainTime; LARGE_INTEGEREndTime; LARGE_INTEGERFrequency; QueryPerformanceFrequency(&Frequency); QueryPerformanceCounter(&BegainTime); Node while(p! =NULL) { Node Node while(q! =NULL) { compare++; if(q->data {index=q;move++;} q=q->next;move++; } if(index! =p)//若第一个就是最小元素,则不用交换 { Ttemp=p->data; p->data=index->data; index->data=temp; move=move+3; } p=p->next;move++; } QueryPerformanceCounter(&EndTime); cout<<"运行时间: "<<(double)(EndTime.QuadPart-BegainTime.QuadPart)/Frequency.QuadPart<<"s"< } 该算法的时间复杂度T(n)=O(n2) 3.程序运行结果 1.测试主函数流程: 正序: 逆序: 乱序: 4.总结 1.调试时出现的问题及解决办法: (1)由于选择的是第二个题目,在存储结构上便不一样,因此课本上的代码只能是仅供参考。 首先我翻出了第一次实验时编写的代码,并稍微改动了一下,使之符合本次试验的要求。 (2)首先是直接插入排序就是一个难点。 一开始我打算利用数组的思想做,但是发现这样链表简直就是一累赘。 于是我改为了指针。 好好理清了思路,一口气写下代码后,发现最后一个数字总是无法正确排入。 我仔细检查,按照代码人工排序后终于发现了错误之所在。 然后冒泡排序和简单选择排序均无难点,对着课本改一下就成了,第二个也是最大的难点便是快速排序。 因为课本上给的代码中需要用到j--,即换到单链表中需要找到一个节点的前驱结点。 这在单链表中是很难实现的,于是我曾出现换成双向链表的想法。 但是一想到换成双向链表整个程序的地基便要换,而且空间复杂度会大幅增加。 于是我上网搜了一下,发现单链表的快速排序是有的,跟课本上改进的快速排序的思想是类似的,但是我还是觉得挺神奇的。 (3)计算时间的算法我没有学过,于是又XX了一下,看大牛们总结的各种计算时间的算法,于是我选了一种精确计算的算法,加进去后便可以计算出精确时间了。 (4)再有就是关键字的统计方面,由于是最后加入,所以从整个程序来看,加入了2个类的成员,用来分别记录比较次数和移动次数。 在具体的函数内部实现上,可能由于测试数据数量太小,线性或者平方的关系表现的并不是很明显。 2.心得体会: 这次编写代码延续了上次编写哈夫曼的良好风格,几乎是全程独自编写,只参考了网上的个别算法思想。 这对我的编程能力又是一次极大的加强,以前编的程序简单,可以参考的代码多,几乎编出来的就已经是正确的,几乎很少调试。 但是现在全是自己编,出现的问题很多,经常编译出来是一长串的问题,即时编译通过,运行时也经常达不到想要的效果,所以不得不多次使用但不调试F11来查找程序错误。 在这个过程中有苦有乐,但是不管怎样,编译通过,运行成功那一时刻的喜悦,我想每一个喜欢编程的人都是能够理解的! 3.下一步的改进: 其实有个第五项其他选项我没有完成,原因是虽然只编4个函数,但已花费了大量时间。 从时间上来说确实是不允许的。 如果时间足够,我想再多编几个函数,实现链表的其他排序。 话又说回来,链表的排序确实没有数组来的方便,我想有机会还是多和书上的数组的排序算法亲近亲近。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C+ 排序