一章排序.ppt
1,第3章 排 序,排序本身涉及的数据结构类型比较单纯，所用的存储结构为顺序表。把排序的内容安排在第 2 章的线性表之后，可巩固第 2 章所学的知识，也有利算法分析能力的提高。 其中有些排序的内容需要树的知识做基础，这些内容被安排在第 6 章来继续学习。例如，堆排序的实现放到 “二叉树的应用”一节；归并排序的跟读需要借助“二叉树遍历”的知识做铺垫等。 讲授本章课程大约需6课时。,2,3.3 先进排序方法,3,三、内部排序的方法,内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,4,二、归并排序,归并排序的过程基于下列基本思想进行： 将两个或两个以上的有序子序列 “归并” 为一个有序序列。,5,在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列,归并为一个记录的有序序列。,有 序 序 列 Rln,有序子序列 Rlm,有序子序列 Rm+1n,这个操作对顺序表而言，是轻而易举的。,6,void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 将有序的记录序列 SRim 和 SRm+1n / 归并为有序的记录序列 TRin / Merge,for (j=m+1, k=i; i=m , / 处理某一个表的剩余尾部,7,if (i=m) TRkn = SRim; / 将剩余的 SRim 复制到 TR,if (j=n) TRkn = SRjn; / 将剩余的 SRjn 复制到 TR,处理某一个表的剩余尾部代码段:,8,归并排序的算法,如果记录无序序列 Rst 的两部分 Rs(s+t)/2 和 R(s+t)/2+1t 已经分别按关键字有序， 则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。,由此，应该先分别对这两部分进行 2-路归并排序。,9,例如：,52, 23, 80, 36, 68, 14 (s=1, t=6), 52, 23, 80 36, 68, 14, 52, 2380, 52, 23, 52, 23, 52, 80,36, 6814,3668,36, 68,14, 36, 68, 14, 23, 36, 52, 68, 80 ,23,10,void Msort ( RcdType SR, RcdType TR1, int s, int t ) / 将SRst 归并排序为 TR1st if (s= =t) TR1s=SRs; else / Msort, / 归并排序的主要操作,11,m = (s+t)/2; / 将SRst平分为SRsm和SRm+1t,Msort (SR, TR2, s, m); / 递归地将SRsm归并为有序的TR2sm Msort (SR, TR2, m+1, t); /递归地SRm+1t归并为有序的TR2m+1t,Merge (TR2, TR1, s, m, t); / 将TR2sm和TR2m+1t归并到TR1st,归并排序主要操作的代码段:,12,理解递归排序算法Msort,13,void MergeSort (SqList / MergeSort,可以得出，对 n 个记录进行归并排序的时间复杂度为(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。,14,（23，52）,（23，52，80）,（36，68）,（ 14， 23， 36， 52， 68， 80）,（14，36，68）,递归归并过程的展开与跟踪,15,15,1. 双向链表,五、其它形式的链表,typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,16,16,最后一个结点的指针域的指针又指回第一个结点的链表,2. 循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,17,17,在循环链表中，头指针也可以改变到指向尾结点，这样用一个头指针就能够控制首位两端，可为有些操作带来便利。,18,18,双向循环链表,空表,非空表,19,19,双向链表的操作特点：,“查询” 和单链表相同。,“插入” 和“删除”时需要同时修改两个方向上的指针。,由于前驱指针的设置，如需要前驱的位置信息时，可直接使用，避免了遍历操作的时间消耗。,20,20,s-next = p-next; p-next = s; s-next-prior = s; s-prior = p;,p,s,插入,21,21,删除,p-next = p-next-next; p-next-prior = p;,p,22,第7次上机作业,1.实现双向链表的插入、删除、输出元素。 2. 实现归并排序。,
