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=newNode;//建立新结点
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*p=front->next;
while（p!
=NULL）
{
cout<data<<"";
p=p->next;
}
cout<}
该算法的时间复杂度为T（n）=O（n）
（3）插入排序算法：
template
voidLinkList:
:
InsertSort（）//升序排列
{
LARGE_INTEGERBegainTime;
LARGE_INTEGEREndTime;
LARGE_INTEGERFrequency;
QueryPerformanceFrequency（&Frequency）;
QueryPerformanceCounter（&BegainTime）;
Node*p1,*p2,*q1,*q2;
Node*s=newNode;
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->datadata）//p2,q1没动
{
Node*temp=q2->next;
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*pos=r;
while（pos!
=front）
{
Node*bound=pos;//本次无序元素的范围
pos=front;move++;
Node*p=front->next;//工作指针
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*first,Node*end）//快速排序，用的是值交换
{
if（first==end）
return;
Node*i,*j;
i=j=first;
while（j!
=end->next）
{
compare++;
if（j->datadata）
{
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*p=front->next;//设立工作指针
while（p!
=NULL）
{
Node*index=p;//假设index是最小的
Node*q=index->next;//设立第二个工作指针
while（q!
=NULL）
{
compare++;
if（q->datadata）
{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个函数，但已花费了大量时间。
从时间上来说确实是不允许的。
如果时间足够，我想再多编几个函数，实现链表的其他排序。
话又说回来，链表的排序确实没有数组来的方便，我想有机会还是多和书上的数组的排序算法亲近亲近。
升级会员 