c++数据结构实验链表排序

1．实验要求实验目的:通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。理解算法的主要思想及流程。实验内容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序（改进型冒泡排序）3、快速排序4、简单选择排序5、堆排序（小根堆）要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main（）函数测试线性表的正确性代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2.程序分析通过排序算法将单链表中的数据进行由小至大（正向排序）存储结构单链表存储数据：structnode{intdata;node*next;}；单链表定义如下：classLinkList{private:node*front;public:LinkList(inta[],intn); 接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针p->next在无序区中指向待插入的结点，在找到插入位置后，将结点p->next插在结点s和p之间。voidLinkList::InsertSort() 速排序：主要通过轴值将数据从两端向中间进行比较，交换以实现排序。通过递归的调用来实现整个链表数据的排序。代码中选用了第一个元素作为轴值。一趟排序的代码：voidLinkList::QSZ(node*b,node*e){if(b->next==e||b==e) 进版的冒泡排序：通过设置pos来记录无序边界的位置以减少比较次数。将数据从前向后两两比较，遇到顺序不对是直接交换两数据的值。每交换一次movef+3；voidLinkList::BubbleSort(){LARGE_INTEGERt1,t2,feq;QueryPerformanceFrequency(&feq); 择排序：每趟排序再待排序的序列中选择关键码最小的元素，顺序添加至已排好的有序序列最后，知道全部记录排序完毕。voidLinkList::SelectSort(){LARGE_INTEGERt1,t2,feq;QueryPerformanceFrequency(&feq); 排序：利用前一趟比较的结果来减少比较次数，提高整体的效率。其中通过链表储存了一棵树。选择使用小根堆进行排序。voidLinkList::sift(intk,intm){inti=k,j=2*i;while(j<=m){comparef++;if(j<m&&(Get(j)->data>Get(j+1)->data)) j++;if(Get(i)->data<Get(j)->data) break;else{turn(Get(i),Get(j));i=j；j=2*i;}}}voidLinkList::heapsort(intn){LARGE_INTEGERt1,t2,feq;QueryPerformanceFrequency(&feq);出结果的函数：voidtell(LinkList&a,LinkList&b,LinkList&c,LinkList&d,LinkList&e){();comparef=0;movef=0;();cout<<"排序结果："；();cout<<"1.插入排序法： Compare："<<setw(3)<<comparef<<";Move："<<setw⑶<<movef<<endl;comparef=0;movef=0;();cout<<"2.改进型冒泡排序法：Compare："<<setw(3)<<comparef<<";Move：<<setw⑶<<movef<<endl;comparef=0;movef=0;();cout<<"3.快速排序法： Compare："<<setw(3)<<comparef<<";Move："<<setw⑶<<movef<<endl;comparef=0;movef=0;();cout<<”4.简单选择排序法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl;comparef=0;movef=0;(10)；cout<<"5.堆排序算法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl;}7.统计时间的函数：#include<>{LARGE_INTEGERt1,t2,feq;QueryPerformanceFrequency(&feq);程序运行结果1.流程图：结束2.测试条件：如果需要对不同的正序，逆序随机序列进行排序，则需要在main函数中进行初始化设置。3.测试结论：SBC:\Windows\system32\cmd.exe正序数明：123456789lt>麋作时IS]为:7.89469B-0071234567S910，排序法： Conipcti'B：45§[SIX：7-«^46Ve-W07:型曾泡排序法：Compare：&3间作埠起眼瑞1.噪2.噪3.澡安舞，|可光;l.Ei?894e-006

啡序法： Compare：45s同为:2.36841B-006

困举拉序法Conpare：54；

间匕?.49995d-00617；Move-Moue：Move：法Compare： 19；Moue： 63列.109H7654221间为：7.89469c-007S：123456789IB序法：Compare： 9；|可为।1.97367e-00G

型冒泡排序法：Compare：

间为:5.52628e-006

排序法：Coware：129；

间为；7.894690-00-?田晅排序，去Oonpare；54

间为：9.0?889e-086MouesSMoveMoue-45Moye：90135I詈间洗一间序省迦异89法叱

7.序9.HF

:4^--Moye：二法Move； 90间塞技累1.操2.噪3.操4.麋5.晴争排序法Conpare：54；Conpare： 29:8.68416e-006怯CompeLi4e= 21继续.一■26105839147

：1.1842e-006

12345G7S910

怯：CornpcLi'e： 29J：l-¥7367e-O061冒泡排序法：Compare：Have«38；Moue-7Moue：Moye：10Move；S44.总结通过这次实验我再次复习了链表的建立及相应的操作，对各类排序算法的实现也有了新的理解，在调试过程中出现了许多问题也花费了很多时间和精力去逐步解决，最后程序运行成功的瞬间真的很开心。问题一：直接插入排序中若是使用从后向前比较插入的话(即书上的办法)难以找到该节点的前驱节点，不方便进行操作，所以最后采用了从前向后进行比较。voidLinkList::InsertSort() 入排序法： Compare：“<<setw(3)<<comparef<<"";Move：""<<setw⑶<<movef<<endl;comparef=0;movef=0;();cout<<"2.改进型冒泡排序法：Compare："<<setw(3)<<comparef<<”;Move：<<setw⑶<<movef<<endl;comparef=0;movef=0;();cout<<"3.快速排序法： Compare："<<setw(3)<<comparef<<";Move："<<setw⑶<<movef<<endl;comparef=0;movef=0;();cout<<”4.简单选择排