实验四排序实验报告

**数据结构实验报告实验名称：实验四排序学生姓名：班级：班内序号：学号：日期：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{结点地址：1000H地址：1020H地址：1080H地址：10C0H头指针**intdata;Node*next;};示意图：2.2关键算法分析一：关键算法(一)直接插入排序voidLinkSort::InsertSort()直接插入排序是插入排序中最简单的排序方法，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好序。（1）算法自然语言1.将整个待排序的记录序列划分成有序区和无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有剩余待排序的记录；2.将无须去的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录；3.重复执行2，直到无序区中没有记录为止。（2）源代码voidLinkSort::InsertSort()//从第二个元素开始，寻找前面那个比它大的intdataNode*next**{Node*P=front-next;//要插入的节点的前驱while(P-next){Node*S=front;//用来比较的节点的前驱while(1){CompareCount++;if(P-next-dataS-next-data)//P的后继比S的后继小则插入{insert(P,S);break;}S=S-next;if(S==P)//若一趟比较结束，且不需要插入{P=P-next;break;}}}**}(3)时间和空间复杂度最好情况下，待排序序列为正序，时间复杂度为O（n）。最坏情况下，待排序序列为逆序，时间复杂度为O（n2）。直接插入排序只需要一个记录的辅助空间，用来作为待插入记录的暂存单元和查找记录的插入位置过程中的“哨兵”。直接插入排序是一种稳定的排序方法。直接插入排序算法简单容易实现，当序列中的记录基本有序或带排序记录较少时，他是最佳的排序方法。但当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率减低。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.将最后一次交换的位置pos，做为下一趟无序区的末尾。4.重复执行2和3，直到无序区中没有反序的记录。（2）源代码voidLinkSort::BubbleSort()**{Node*P=front-next;while(P-next)//第一趟排序并查找无序范围{CompareCount++;if(P-dataP-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-dataP-next-data)**{swap(P,P-next);pos=P-next;}P=P-next;}P=front-next;}}(3)时间和空间复杂度在最好情况下，待排序记录序列为正序，算法只执行了一趟，进行了n-1次关键码的比较，不需要移动记录，时间复杂度为O（n）；在最坏情况下，待排序记录序列为反序，时间复杂度为O（n2），空间复杂度为O(1)。冒泡排序是一种稳定的排序方法。rjrj+1ri+1≤……≤rn-1≤rn无序区有序区1≤j≤i-1已经位于最终位置起泡排序的基本思想反序则交换初始键值序列［5013559727384965］第一趟排序结果［13505527384965］97第二趟排序结果［1350273849］556597第三趟排序结果［13273849］50556597第四趟排序结果1327384950556597冒泡排序过程**（三）快速排序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-dataP-next-data)//元素值小于轴点值，则将该元素插在轴点之前{if(P-next==End)//若该元素为End，则将其前驱设为EndEnd=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.在无序区中选取关键码最小的记录，将它与无序区中的第一个记录交换，使得有序区扩展了一个记录，而无序区减少了一个记录。[r1……ri-1]ri[ri+1……rn]均≤ri轴值均≥ri位于最终位置快速排序的基本思想图解**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-dataMin-next-data)Min=P;P=P-next;}insert(Min,S);S=S-next;}}**（3）时间和空间复杂度简单选择排序最好、最坏和平均的时间复杂度为O（n2）。简单选择排序是一种不稳定的排序方法。（五）输出比较结果函数（含计算函数体执行时间代码）（1）算法自然语言1、依次调用直接插入排序、冒泡排序、快速排序、简单选择排序的函数体，进行序列的排序，并输出相应的比较次数、移动次数。2、获取当前系统时间。在调用函数之前设定一个调用代码前的时间，在调用函数之后再次初始键值序列［49276597761338］第一趟排序结果13［276597764938］第二趟排序结果1327［6597764938］第三趟排序结果132738［97764965］第四趟排序结果13273849［769765］第五趟排序结果1327384965［9776］第六趟排序结果13273849657697简单选择排序的过程示例**设定一个调用代码后的时间，两个时间相减就是代码运行时间。说明：运用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();cout1.插入。比较次数：setw(3)CompareCount;移动次数：setw(3)MoveCount;时间:TimeCountusendl;CompareCount=0;MoveCount=0;TimeCount=0;QueryPerformanceCounter(&time_start);//记录起始时间b.BubbleSort();QueryPerformanceCounter(&time_over);//记录结束时间TimeCount=((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;cout2.冒泡。比较次数：setw(3)CompareCount;移动次数：setw(3)MoveCount;时间:TimeCountusendl;CompareCount=0;MoveCount=0;TimeCount=0;QueryPerformanceCounter(&time_start);//记录起始时间c.Qso