C++数据结构之链表排序

1、2009级数据结构实验报告实验名称：使用链表实现各种排序算法学生姓名：桂树易班级：2009211120班内序号：07学号：09210580日期：2010年12月19日1.实验要求【实验目的】通过选择实验内容中的两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法的使用的情况。【实验内容】使用链表实现下面各种排序算法，并进行比较。排序算法如下：插入排序；冒泡排序；快速排序；简单选择排序；其他。具体要求如下。测试数据分成三类：正序、逆序、随机数据。对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。对于这三类数据，比较上述排序算法

2、中不同算法的执行时间，精确到微秒（选作）。对和的结果进行分析，验证上述各种算法的时间复杂度。编写main（）函数测试各种排序算法的正确性。2.程序分析2.1 存储结构存储结构：链表lastfirstFH现I卜市1J,碗八first-八last2.2 关键算法分析【设计思想】以直接插入排序为例：首先将待排序数据建立一个带头结点的单链表。在单链表中进行直接插入排序的基本思想是：将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针q在无序区中指向待插入的

3、结点，为了查找正确的插入位置，每趟排序前需将工作指针pre和p指向头结点和开始结点，在找到插入位置后，将结点q插在结点pre和p之间。这相当于在单链表中删除结点q,因此为了保证链表不断开，须在删除结点q之前保留结点q的后继结点的地址。【复杂度】(1)建立链表存储数据的算法：Node*CreateSortNode(intcount,int*array)(Node*p1,*p2,*head;inti;head=NULL;for(i=0;i<count;i+)p1=newNode;p1->data=arrayi;p1->next=NULL;if(i=0)head=p1;elsep2

4、->next=p1;p2=p1；)p2->next=NULL;returnhead;)该算法的时间复杂度为T(N)=O(N)(2)输出数据的算法：voidListSortNode(Node*start)Node*p;p=start;while(p!=NULL)cout<<p->data<<'0'p=p->next;)cout<<endl;)该算法的时间复杂度T(N)=O(N)(3)插入排序算法：Node*Insert_Sort_LinkTable(Node*head)_LARGE_INTEGERtime_start;_

5、LARGE_INTEGERtime_over;doubledqFreq;LARGE_INTEGERf;QueryPerformanceFrequency(&f);dqFreq=(double)f.QuadPart;QueryPerformanceCounter(&time_start);Node*s,*newhead,*p,*pre,*min;s=head;newhead=NULL;b1+=2;while(s!=NULL)a1+,b1+=3;min=s;p=newhead;while(p!=NULL&&p->data<min->data)pre

6、=p,p=p->next;b1+=2,a1+=2;s=s->next;if(p=newhead)(a1+,b1+=2;newhead=min;newhead->next=p;)else(a1+,b1+=2;pre->next=min;min->next=p;)QueryPerformanceCounter(&time_over);returnnewhead;)该算法的时间复杂度T(N)=O(N2)(4)冒泡排序算法：Node*Ebullient_Sort_LinkTable(Node*head)(_LARGE_INTEGERtime_start;_LARG

7、E_INTEGERtime_over;doubledqFreq;LARGE_INTEGERf;QueryPerformanceFrequency(&f);dqFreq=(double)f.QuadPart;QueryPerformanceCounter(&time_start);Node*q,*tail,*p,*t;q=newNode;q->next=head;head=q;b2+=3;for(tail=NULL;tail!=head;tail=p)(b2+=2,a2+=2;for(p=q=head;q->next->next!=tail;q=q->ne

8、xt)(b2+=3,a2+=2;if(q->next->data>q->next->next->data)(a2+,b2+=5;t=q->next->next;q->next->next=t->next;t->next=q->next;q->next=t;p=q->next->next;)q=head;head=head->next;b2+=2;deleteq;QueryPerformanceCounter(&time_over);returnhead;)该算法的时间复杂度T(N)=O

9、(N2)(5)快速排序算法：Node*Fast_Sort_LinkTable(Node*head,Node*tail)_LARGE_INTEGERtime_start;_LARGE_INTEGERtime_over;doubledqFreq;LARGE_INTEGERf;QueryPerformanceFrequency(&f);dqFreq=(double)f.QuadPart;QueryPerformanceCounter(&time_start);if(head=NULL|tail=NULL)returnNULL;if(head=tail)returnNULL;Node*

10、p,*r,*pre;pre=head;p=head->next;r=head;b3+=3;while(p&&p!=tail->next)a3+=2;if(p->data<=head->data)a3+,b3+=5;r=pre;pre=pre->next;swamp(pre->data,p->data);)p=p->next;b3+;swamp(head->data,pre->data);b3+=3;Fast_Sort_LinkTable(head,r);Fast_Sort_LinkTable(pre->ne

11、xt,tail);QueryPerformanceCounter(&time_over);returnhead;该算法的时间复杂度T(N)=O(NlogN)(6)简单选择排序算法：Node*Select_Sort_LinkTable(Node*head)_LARGE_INTEGERtime_start;_LARGE_INTEGERtime_over;doubledqFreq;LARGE_INTEGERf;QueryPerformanceFrequency(&f);dqFreq=(double)f.QuadPart;QueryPerformanceCounter(&tim

12、e_start);Node*newhead,*tail,*p,*pre,*min;newhead=NULL;b4+;while(head!=NULL)a4+;for(p=min=head;p->next!=NULL;p=p->next)a4+,b4+=3;if(p->next->data<min->data)a4+,b4+=2;pre=p;min=p->next;if(min=head)head=head->next;a4+,b4+;elsepre->next=min->next;a4+,b4+;if(newhead=NULL)tai

13、l=newhead=min;a4+,b4+;elsetail=tail->next=min;a4+,b4+;if(newhead!=NULL)tail->next=NULL;a4+,b4+;QueryPerformanceCounter(&time_over);returnnewhead;)该算法的时间复杂度T(N)=O(N2)2.3其他由于程序源代码在上述时间复杂度分析中已基本全部提及，此处不再附加。3.程序运行结果1.测试主函数流程:士C!U«rsgkyD«sktopm£5Bt5lSE3&ORTDebugsort.*xe犍表实现各排

14、序算法姓名;桂树易班级2碘921112目学号:晒的至睛X二不足至蔡宿月还标尾不贰10请输入第1个数45请输入第2个数E78请输入第3个数22请输入第4个数卷输入第5个数髯输入第6个数9B请输入第M数请输入第8个数卷输入第y个数234请输入第1。个数7«90?.数数:次次置动移:运关关结8试的的的的9调ly!tt77续卜,Ar:r,:IZAL1大£于丰Afl6组泡泡泡泡5需2胃冒胃冒SIS”请89键7车78回6按择出选输人泡速黑出插目艮间，*，123456卜青选择你需要进行的操作:简单选择排序的运行时间是:：1.58033e-005-t#间单选4556779823467878

15、90!乍业谯四双a&CiRTDbug«5rt看x*7188w62e16301R36100:898回键果9-T.245S2快快耍快嗖快快快快快快2选选选选2继117次次次次次次次次.次次次速壹17单单单单17需4日皆喜暮皆香皆香皆费数8时罡舌AE!3'-m1m_1m-m.17-nJ-3-mLm-mJm.2b5it=IE一JLEyJLlElr-JL1;y”Jr一一1F内-田5;JLJlr一，JL-H-i-s同4丰三，于三，亨三.壬三三壬必与N4主丰丰本4阴2速速速速速速速速WWt2112续41111111100E_二r二rn，Ill千工nK9一丁-丁一丁-丁-丁-丁-丁-

16、丁-ZE77运运运运运运运运运运LSX舌在77运关关结77酊由向由向向向内内向内声卷内向内向SLb;rTrITTITT,rTTIT1.rrr-.To,TnjnITT出地E丁Lb-JrrTTrrT.rr"r6尸w关奎s试曾否ae2.数数:次次2 .测试条件：如上图所示，输入的数据为10个乱序数据45,678,22,4,17,98,77,56,234,780。3 .测试结论：依次测试了插入排序，冒泡排序，快速排序，简单选择排序，结果都为正序，而且全部给出了算法运行时间和关键字的比较及移动次数，应可得出函数正常工作的结论。4.总结1 .调试时出现的问题及解决办法：(1)由于选择的是第二个，

17、书上没有任何的参考代码，甚至在一些存储和实现方法上由于使用的是链表，因而出现了和数组不太一样的思想。遇到的第一个难题是插入排序，因为使用的是单链表，不可能从后往前遍历，所以不适合使用书上的插入排序算法，对此我做了一些调整，把每次往前寻找改成每次从头往后寻找合适的插入点，由于测试数据包括正序、乱序、逆序，因此这样修改并不会导致算法整体时间复杂度的增加。(2)第二个遇到的问题是快速排序算法，按照书上的算法，快速排序需要从双向往中间靠拢，最后定下权值的位置，对此我曾一度想要改成用双向链表存储数据以实现书上的算法。但是后来感觉到这样会使整个程序显得异常臃肿(编完还需要加入时间算法和关键字统计算法)，于

18、是我又上网搜了一下，发现单链表的快速排序是有的，和书上的改进的快速排序算法思想是一样的，先将所有的数据根据权值左右分开，最后留下中间的位置给权值，然后不断递归求得最终结果。根据这个思想我顺利地编出了快速排序的算法。(3)在加入时间函数的时候也出现了一些问题，这主要是由于缺乏经验，不知道什么样的函数能够显示微秒级别的程序运行时间，这个问题在和同学讨论并上网搜索的过程中顺利地解决了。(4)再有就是关键字的统计方面，由于是最后加入，所以从整个程序来看，加入了8个静态全局变量，用来分别记录4个排序算法的关键字比较次数和移动次数。在具体的函数内部实现上，可能由于测试数据数量太小，线性或者平方的关系表现的并不是很明显。2 .心得体会：这次编写代码延续了上次编写哈夫曼的良好风格，几乎是全程独自编写，只参考了网上的个别算法思想。这对我的编程能力又是一次极大的加强，以前编的程序简单，可以参考的代码多，