实验四排序实验报告

数据构造实验报告实验名称：实验四排序学生姓名：班级：班内序号：学号：日期：12月21日实验规定题目2使用链表实现下面多个排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序3、快速排序4、简朴选择排序5、其它规定：1、测试数据分成三类：正序、逆序、随机数据。2、对于这三类数据，比较上述排序算法中核心字的比较次数和移动次数（其中核心字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）。4、对2和3的成果进行分析，验证上述多个算法的时间复杂度。编写测试main()函数测试线性表的对的性。2、程序分析2.1存储构造阐明：本程序排序序列的存储由链表来完毕。其存储构造以下图所示。(1)单链表存储构造：结点地址：1000HA[2]结点地址：1000H1080H……头指针地址：1020HA[0]头指针地址：1020H10C0H……地址：1080HA[3]地址：1080HNULL……地址：10C0HA[1]地址：10C0H1000H……（2）结点构造structNode{ intdata; Node*next;};示意图：intdataNode*next intdataNode*next2.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<S->next->data) //P的后继比S的后继小则插入 { insert(P,S); break; } S=S->next; if(S==P) //若一趟比较结束，且不需要插入 { P=P->next; break;} } }}(3)时间和空间复杂度最佳状况下，待排序序列为正序，时间复杂度为O（n）。最坏状况下，待排序序列为逆序，时间复杂度为O（n2）。直接插入排序只需要一种统计的辅助空间，用来作为待插入统计的暂存单元和查找统计的插入位置过程中的“哨兵”。直接插入排序是一种稳定的排序办法。直接插入排序算法简朴容易实现，当序列中的统计基本有序或带排序统计较少时，他是最佳的排序办法。但当待排序的统计个数较多时，大量的比较和移动操作使直接插入排序算法的效率减低。rr1≤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->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)。 冒泡排序是一种稳定的排序办法。rrjrj+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->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）。 快速排序是一种不稳定的排序办法。[[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->next->next) { Node*P=S; Node*Min=P; while(P->next)//查找最小统计的位置 { CompareCount++; if(P->next->data<Min->next->data) Min=P; P=P->next; } insert(Min,S); S=S->next; }}（3）时间和空间复杂度简朴选择排序最佳、最坏和平均的时间复杂度为O（n2）。简朴选择排序是一种不稳定的排序办法。初始键值序列初始键值序列［49276597761338］第一趟排序成果13［276597764938］第二趟排序成果1327［6597764938］第三趟排序成果132738［97764965］第四趟排序成果13273849［769765］第五趟排序成果1327384965［9776］第六趟排序成果13273849657697简朴选择排序的过程示例（五）输出比较成果函数（含计算函数体执行时间代码）（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.插入。比较次数："<<setw(3)<<CompareCount<<";移动次数："<<setw(3)<<MoveCount<<";时间:"<<TimeCount<<"us"<<endl; 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.冒泡。比较次数："<<setw(3)<<CompareCount<<";移动次数："<<setw(3)<<MoveCount<<";时间:"<<TimeCount<<"us"<<endl; 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.快速。比较次数："<<setw(3)<<CompareCount<<";移动次数："<<setw(3)<<MoveCount<<";时间:"<<TimeCount<<"us"<<endl; 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.选择。比较次数："<<setw(3)<<CompareCount<<";移动次数："<<setw(3)<<MoveCount<<";时间:"<<TimeCount<<"us"<<endl;}（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(nlog2