用链表实现排序

北京邮电大学信息与通信工程学院2009级数据结构实验报告1. 实验要求实验目的:学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 实验内容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字 交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main（）函数测试线性表的正确性2. 程序分析2.1存储结构双循环链表:2.2关键算法分析1.算法设计思想：（1）冒泡排序：将数组 a0,1,?, n-1看做是垂直排列的，每个元素值看做该气泡的重量，因为轻重量的气泡不能在重重量之下，所以从最后一个气泡开始和其前面一个比较，若下面的轻则交换，如此反复直到所有轻气泡都在上面，重的都在下面为止。（2）选择排序：第一次循环从0的位置开始找所有元素中最小，与0位置元素交换？第i 次循环从 i-1 的位置开始往后找此时最小元素与i-1 元素交换，直到所有的都循环完。( 3) 插入排序： 像揭牌一样， 设第一个元素是排好序的， 第二个元素和第一个元素比较 找到它的位置?第 i 个元素和之前排好的 i-1 个元素比较找到自己的位置， 直到所有的元素都 排序完毕。( 4) 快速排序： 取第一个元素做基准， 将所有元素分成左右两部分， 用分治法分别对两 边排序，然后将两边分别排序好的两组元素再按大小顺序合并成一个数组。用链表做只要把数组换成链表就可以了，代码的思想还是不变的。1) 插入排序：while(p!=front)m=p-data ;x+; / 用于计比较次数的计数器if(m prior-data )s=p-prior;while(s!=front&s-data m)s-next -data =s-data ; s=s-prior ; x+;y+;/ 用于计移动次数的计数器s-next -data =m;y+; p=p-next ;2) 冒泡排序：while(p!=front)s=p;/s 表示本次排序无序元素的范围第7页p=front; r=front-next ; while(r!=s)x+;if(r-data r-next -data ) m=r-data ; r-data =r-next -data ; r-next -data =m; p=r;y+=3;r=r-next ;/相邻元素进行比较/元素交换3) 一趟快速排序：int pivot=p-data ;/选取基准元素while(p!=q) while(p!=q)&(q-data =pivot) /右侧扫描，查找小于轴值的元素(*x)+;q=q-prior ;p-data =q-data ;(*y)+;while(p!=q)&(p-data next ;q-data =p-data ;(*y)+;p-data =pivot;return p; / 返回轴值所在的位置4) 简单选择排序：while(p!=front-prior )s=p;/假设 s 所指元素是最小的r=s-next ;while(r!=front)/ 查找最小值的位置x+;if(r-data data )s=r;r=r-next ;if(s!=p)/若第一个就是最小元素，则不用交换m=p-data ;p-data =s-data ;s-data =m;y+=3;p=p-next ;3. 程序运行结果1MU1U9.84 M169*9b9610刁1001001S1S01Q05 2 : 2 = 2 G 22 5_= S 9 i2 tf 5 :tr8 904I 52s53JI 8 35 s 326寸亍：2ITT VKz.6w _2 t.2S7文 k c % hs L - T - G- 、-u 丄-=罔J琵；运出2比-i =测34ssfftAfts结JW2A人雪也專速序单善DLl43徘冒 r= 决徒517y6 蚤 -务5 - 亂變位若位: t73单9.41单典41单话 4 毀4 IE LL 43-3 女 3 3 联t)搂-zT 灵2电丸2 3 : 耳2 晋聘冷橐位I -E- 4 A 4 4舍 5 4 I ? I I ? I 5xll- 4 5? 7 2 7? 4 9 - ! 92 fi 改6 i 3 fc 6111裁円1数73丿數73驚732 2 2 22專斤 丘黑E位4 豹4 4 4rir 5 43 sxt 5 -if 5 :fv 5 4 56 位 * 位 1 t、57r 6 .1 : 6 4单544单-15气单9fl叫间数4 卜 4-( 4寸夂43 ： 3 QW32273一霍1Y雳11賤11漆11 tEhk运比 I 0人人垢也專速序单7位2位；位3( 5& 4 5 ynF 4 b-3- 1 5 可戈 :s 2 3 耳 1 n 9 Jy 9 t 6V 8 0 95 4 54 5 firH 2 -LT y 9 2 22 s2 a5i717v7 谪?5时S2对次乂対欢2运比2 测5-濟15_.石15_.鎭甞脣15 的丄运比H运比.-运比I 列辭隹果仔底果笛臬麗果 排7 进选经 机2入入腐泡序单舌由程序结果可以验证：1）各种排序算法的比较次数和移动次数满足它们时间复杂度的最好、最坏和平均情况，它们的性能如下：排序方法平均情况最好情况最坏情况插入排序0(n2)0(n)0(n2)冒泡排序0(n2)0(n)0(n2)快速排序O(nl og2 n)O(nlog 2n)0(n2)简单选择排序0(n2)0(n2)0(n2)2） 正序、逆序和随机序列的结果都是快速排序比其他三种用的时间长，其他三种用的时 间相差不大。我认为快速排序慢的原因一方面是它的比较次数确实比其他三种的要多，另-方面由于它用到了递归，并且也调用了别的函数（Partion函数），在调用函数时进出栈耗去了一些时间，使程序用时增加。4总结排序过程通常要进行下列两种基本操作1关键码之间的比较 2移动;记录从一个位置移动到另一个位置。所以在待排序的个数一定的情况下，算法的执行时间主要消耗在关键码之间的比较和记录的移动上，因此高效率的算法应该尽可能少的关键码比较次数和记录的移动 次数。评价排序算法的另一个主要指标是执行算法所需要的辅助存储空间通过这次试验我更好的体会到排序的各种方法以及其比较所需的时间，对于不同的排序选择可以更好的应用。 对于调试时出现的问题及解决的方法，为了得到快速排序中的移动次数和比较次数，由于它是递归，所以若要直接用整型的计数器，则需将每一次计数的结果返回给调用它的函数， 但一个函数又不能同时返回两个值，后来想到可以在函数参数中加两个整型的指针，通过地址传递，直接修改这两个指针所指元素的值，这样就不用返回什么，也 实现了计移动次数和比较次数的目的。