实验四 排序 实验报告材料.doc

《实验四 排序 实验报告材料.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告实验名称：实验四排序学生：班级：班序号：学号：日期：2012年12月21日1、实验要求题目2使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据。2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）。4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。编写测试

2、main()函数测试线性表的正确性。2、程序分析2.1存储结构说明：本程序排序序列的存储由链表来完成。其存储结构如下图所示。(1)单链表存储结构：结点地址：1000HA[2]1080H……头指针地址：1020HA[0]10C0H……地址：1080HA[3]NULL……地址：10C0HA[1]1000H……（2）结点结构structNode{intdata;Node*next;};示意图：intdataNode*next2.2关键算法分析一：关键算法(一)直接插入排序voidLinkSort::Insert

3、Sort()直接插入排序是插入排序中最简单的排序方法，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好序。（1）算法自然语言1.将整个待排序的记录序列划分成有序区和无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有剩余待排序的记录；2.将无须去的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录；3.重复执行2，直到无序区中没有记录为止。（2）源代码voidLinkSort::InsertSort()//从第二个元素开始

4、，寻找前面那个比它大的{Node*P=front->next;//要插入的节点的前驱while(P->next){Node*S=front;//用来比较的节点的前驱while(1){CompareCount++;if(P->next->datanext->data)//P的后继比S的后继小则插入{insert(P,S);break;}S=S->next;if(S==P)//若一趟比较结束，且不需要插入{P=P->next;break;}}}}(3)时间和空间复杂度最好情况下，待排序序列为正序，时间

5、复杂度为O（n）。最坏情况下，待排序序列为逆序，时间复杂度为O（n2）。直接插入排序只需要一个记录的辅助空间，用来作为待插入记录的暂存单元和查找记录的插入位置过程中的“哨兵”。直接插入排序是一种稳定的排序方法。直接插入排序算法简单容易实现，当序列中的记录基本有序或带排序记录较少时，他是最佳的排序方法。但当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率减低。（二）冒泡排序voidLinkSort::BubbleSort()冒泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻

6、记录的关键码，如果反序则交换，直到没有反序的记录为止。本程序采用改进的冒泡程序。（1）算法自然语言1.将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。2.对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得关键码小的记录向前移，关键码大的记录向后移（像水中的气泡，体积大的先浮上来）。3.将最后一次交换的位置pos，做为下一趟无序区的末尾。4.重复执行2和3，直到无序区中没有反序的记录。（2）源代码voidLinkSort::BubbleSort

7、(){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->d

8、ata){swap(P,P->next);pos=P->next;}P=P->next;}P=front->next;}}(3)时间和空间复杂度在最好情况下，待排序记录序列为正序，算法只执行了一趟，进行了n-1次关键码的比较，不需要移动记录，时间复杂度为O（n）；在最坏情况下，待排序记录序列为反序，时间复杂度为O（n2），空间复杂度为O(1)。冒泡排序是一种稳定的排序方法。初始键值序列［5013559727384965］第一趟