用链表实现排序.doc

《用链表实现排序.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2009级数据结构实验报告1.实验要求l实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。l实验内容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述

2、各种算法的时间复杂度编写测试main()函数测试线性表的正确性2.程序分析2.1存储结构双循环链表：a1ana2front……2.2关键算法分析1.算法设计思想：（1）冒泡排序：将数组a[0,1,•••,n-1]看做是垂直排列的，每个元素值看做该气泡的重量，因为轻重量的气泡不能在重重量之下，所以从最后一个气泡开始和其前面一个比较，若下面的轻则交换，如此反复直到所有轻气泡都在上面，重的都在下面为止。（2）选择排序：第一次循环从0的位置开始找所有元素中最小，与0位置元素交换•••第i次循环从i-1的位置开始

3、往后找此时最小元素与i-1元素交换，直到所有的都循环完。（3）插入排序：像揭牌一样，设第一个元素是排好序的，第二个元素和第一个元素比较找到它的位置••••第i个元素和之前排好的i-1个元素比较找到自己的位置，直到所有的元素都排序完毕。（4）快速排序：取第一个元素做基准，将所有元素分成左右两部分，用分治法分别对两边排序，然后将两边分别排序好的两组元素再按大小顺序合并成一个数组。用链表做只要把数组换成链表就可以了，代码的思想还是不变的。1）插入排序：while(p!=front){m=p->data;x++

4、;//用于计比较次数的计数器if(mprior->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表示本次排序无序元素的范围p=front;r=front->next;while(r!=s){x++;if(r->data>r-

5、>next->data)//相邻元素进行比较{m=r->data;//元素交换r->data=r->next->data;r->next->data=m;p=r;y+=3;}r=r->next;}}3）一趟快速排序：intpivot=p->data;//选取基准元素while(p!=q){while((p!=q)&&(q->data>=pivot))//右侧扫描，查找小于轴值的元素{(*x)++;q=q->prior;}p->data=q->data;(*y)++;while((p!=q)&&(p->d

6、ata<=pivot))//左侧扫描，查找大于轴值的元素{(*x)++;p=p->next;}q->data=p->data;(*y)++;}p->data=pivot;returnp;//返回轴值所在的位置4）简单选择排序：while(p!=front->prior){s=p;//假设s所指元素是最小的r=s->next;while(r!=front)//查找最小值的位置{x++;if(r->datadata)s=r;r=r->next;}if(s!=p)//若第一个就是最小元素，则不用交换{

7、m=p->data;p->data=s->data;s->data=m;y+=3;}p=p->next;}3.程序运行结果由程序结果可以验证：1)各种排序算法的比较次数和移动次数满足它们时间复杂度的最好、最坏和平均情况，它们的性能如下：排序方法平均情况最好情况最坏情况插入排序O(n2)O(n)O(n2)冒泡排序O(n2)O(n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)简单选择排序O(n2)O(n2)O(n2)2）正序、逆序和随机序列的结果都是快速排序比其他三种用的时间长，其他三种

8、用的时间相差不大。我认为快速排序慢的原因一方面是它的比较次数确实比其他三种的要多，另一方面由于它用到了递归，并且也调用了别的函数（Partion函数），在调用函数时进出栈耗去了一些时间，使程序用时增加。4.总结排序过程通常要进行下列两种基本操作1.关键码之间的比较2.移动;记录从一个位置移动到另一个位置。所以在待排序的个数一定的情况下，算法的执行时间主要消耗在关键码之间的比较和记录的移动上，因此高效率的算法应该尽可能少的关键码比较次数和记录