第10章数据结构排序课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第10章数据结构排序课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 10 数据结构 排序 课件
- 资源描述:
-
1、1第10章 排序 陈守孔陈守孔 孟佳娜孟佳娜 陈卓陈卓2本章目录w 10.1 概述概述w 10.2 插入排序插入排序 n 10.2.1 直接插入排序直接插入排序 n 10.2.2 折半插入排序折半插入排序 *10.2.3 二路插入排序二路插入排序 *10.2.4 表插入排序表插入排序 n 10.2.5 希尔排序希尔排序w 10.3 交换排序交换排序 n 10.3.1 起泡排序起泡排序 n 10.3.2 快速排序快速排序w 10.4 选择排序选择排序 n10.4.1 直接选择排序直接选择排序 n10.4.2 树形选择排序树形选择排序n10.4.3 堆排序堆排序w 10.5 归并排序归并排序w 1
2、0.6 分配排序分配排序w 10.7 内部排序方法的比较内部排序方法的比较w 10.8 外部排序外部排序 n 10.8.1 文件管理文件管理 10.8.2 外部排序外部排序 10.8.3 多路归并排序多路归并排序 n 10.8.4 置换选择排序置换选择排序 *10.8.5 最佳归并树最佳归并树 *10.8.6 磁带排序磁带排序3主要内容w知识点知识点w1、排序的定义,排序可以看作是线性表的一种操作排序的定义,排序可以看作是线性表的一种操作w2、排序的分类,稳定排序与不稳定排序的定义。、排序的分类,稳定排序与不稳定排序的定义。w3、插入排序(直接插入、插入排序(直接插入、对分插入对分插入、二路插
3、入、表插入、希尔插、二路插入、表插入、希尔插入排序)。入排序)。w4、交换排序(冒泡排序、交换排序(冒泡排序、快速排序快速排序)。)。w5、选择排序(简单选择排序、树形选择排序、选择排序(简单选择排序、树形选择排序、堆排序堆排序)。)。w6、归并排序、基数排序。、归并排序、基数排序。w7、外部排序、外部排序w重点难点重点难点w1、各种排序所基于的基本思想。、各种排序所基于的基本思想。w2、排序性能的分析,是否是稳定排序。、排序性能的分析,是否是稳定排序。w3、折半插入、希尔排序折半插入、希尔排序。w4、快速排序快速排序。w5、堆排序堆排序。w6、败者树、置换选择排序、败者树、置换选择排序、最佳
4、归并树最佳归并树。w7、对每种排序方法的学习,能举一反三。、对每种排序方法的学习,能举一反三。4基本概念 w 排序:排序:假设含假设含n个记录的序列为个记录的序列为R1,R2,Rn,其相应的关键字序列为其相应的关键字序列为 K1,K2,Kn,这些关键字相互之间可以进行比较,即在它这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系们之间存在着这样一个关系Ks1Ks2Ksn,按此固有关系将按此固有关系将n个记录的序列重新排列为个记录的序列重新排列为 Rs1,Rs2,Rsn 的操作称作排序。的操作称作排序。5基本概念稳定排序稳定排序:若若Ki为关键字,为关键字,Ki=Kj(ij),且在)
5、,且在排序前的序列中排序前的序列中Ri领先于领先于Rj。经过排序后,。经过排序后,Ri与与Rj的相对次序保持不变(即的相对次序保持不变(即Ri仍领先于仍领先于Rj),则称这),则称这种排序方法是种排序方法是稳定的稳定的,否则称之为,否则称之为不稳定的。不稳定的。内部排序内部排序 :若整个排序过程不需要访问外存便能完:若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序成,则称此类排序问题为内部排序 外部排序外部排序:若参加排序的记录数量很大,整个序列:若参加排序的记录数量很大,整个序列的排序过程不可能一次在内存中完成,则称此类排的排序过程不可能一次在内存中完成,则称此类排序问题为外
6、部排序序问题为外部排序 6排序的类型定义#define n 待排序记录的个数待排序记录的个数typedef struct int key;AnyType other;记录其它数据域记录其它数据域 RecType;RecType Rn+1;7基本思想基本思想:假定第一个记录有序假定第一个记录有序,从第从第2 2个记录开个记录开始,将待排序的记录插入到有序序列中,使有序序始,将待排序的记录插入到有序序列中,使有序序列逐渐扩大,直至所有记录都进入有序序列中。列逐渐扩大,直至所有记录都进入有序序列中。插入排序 插入排序种类插入排序种类:直接插入排序直接插入排序 折半插入排序折半插入排序 二路插入排序二
7、路插入排序 表插入排序表插入排序 希尔排序希尔排序 8直接插入排序基本思想基本思想:将记录Ri(2=i=n)插入到有序子序列R1.i-1中,使记录的有序序列从R1.i-1变为R1.i 9示例初始关键字序列:51 33 62 96 87 17 28 51i=2(33)33 51 62 96 87 17 28 51i=3(62)33 51 62 96 87 17 28 51i=4(96)33 51 62 96 87 17 28 51i=5(87)33 51 62 87 96 17 28 51i=6(17)17 33 51 62 87 96 28 51i=7(28)17 28 33 51 62 87
8、 96 51i=8(51)17 28 33 51 51 62 87 9610一趟直接插入排序算法void StrOnePass(RecType R,int i)已知已知R1.i-1中的记录按关键字非递减有序排列,本算法中的记录按关键字非递减有序排列,本算法 插入插入Ri,使使R1.i中的记录按关键字非递减有序排列中的记录按关键字非递减有序排列 R0=Ri;j=i-1;将待排序记录放进监视哨将待排序记录放进监视哨 x=R0.key;从后向前查找插入位置,将大于待排序记录向后移动从后向前查找插入位置,将大于待排序记录向后移动 while(x Rj.key)Rj+1=Rj;j-;记录后移记录后移 R
9、j+1=R0;将待排序记录放到合适位置将待排序记录放到合适位置 StrOnePass11直接插入排序算法void StrInsSort1(RecType R,int n)本算法对本算法对R1.n进行直接插入排序进行直接插入排序 for(i=2;i=n;i+)假定第一个记录有序假定第一个记录有序 StrOnePass(R,i);12直接插入排序性能分析w 最好情况最好情况比较次数为n1次移动次数为2(n1)次w最坏情况最坏情况比较次数为 =(n+2)(n-1)/2 n2ii移动次数为 =(n+4)(n-1)/2 n2)21(ii13折半插入排序折半插入排序w void BinsSort(RecT
10、ype R,int n)w 对对R1.n进行折半插入排序进行折半插入排序w for(i=2;i=n;i+)假定第一个记录有序假定第一个记录有序 w R0=Ri;将待排记录将待排记录Ri暂存到暂存到R0w low=1;high=i-1;设置折半查找的范围设置折半查找的范围 Rlow.highw while(low=high)w m=(low+high)/2;折半折半w if(R0.keyhigh;j-)Rj+1=Rj;记录后移记录后移w Rhigh+1=R0;插入插入w forw BinsSort14折半插入排序性能分析折半插入排序性能分析w 减少了比较次数,移动次数不变。w 时间复杂度仍为O(
11、n2)。15 在对一组记录在对一组记录(5454,3838,9696,2323,1515,7272,6060,4545,8383)进行直接排序时,当把第进行直接排序时,当把第7 7个记录个记录6060插入插入到有序表时,为寻找插入位置需比较多少到有序表时,为寻找插入位置需比较多少次次16二路插入排序二路插入排序w 对折半插入排序改进,减少了移动记录的次数,对折半插入排序改进,减少了移动记录的次数,但它要借助但它要借助n个记录的辅助空间,即其空间复杂个记录的辅助空间,即其空间复杂度为度为O(n)。)。w 基本思想:另设一数组基本思想:另设一数组d,将,将R1赋值给赋值给d1,并将并将d1看作排好
12、序的中间记录,从第二个记录看作排好序的中间记录,从第二个记录起依次将关键字小于起依次将关键字小于d1的记录插入的记录插入d1之前的之前的有序序列,将关键字大于有序序列,将关键字大于d1的记录插入的记录插入d1之之后的有序序列。后的有序序列。w 借助两个变量借助两个变量first和和final来指示排序过程中有序来指示排序过程中有序序列第一个记录和最后一个记录在序列第一个记录和最后一个记录在d中的位置。中的位置。17w 初始关键字序列:初始关键字序列:51 33 62 96 87 17 28 51 w i=1 51w firstfinalw i=2 51 33w final firstw i=3
13、 51 62 33w final firstw i=4 51 62 96 33w final firstw i=5 51 62 87 96 33w final firstw i=6 51 62 87 96 17 33w final first w i=7 51 62 87 96 17 28 33w final first w i=8 51 51 62 87 96 17 28 33w final first 18二路插入排序算法二路插入排序算法w void BiInsertSort(RecType R,int n)w 二路插入排序的算法二路插入排序的算法w int dn+1;辅助存储辅助存储w
14、d1=R1;first=1;final=1;w for(i=2;i=d1.key)插入后部插入后部w low=1;high=final;w while(low=high)折半查找插入位置折半查找插入位置w m=(low+high)/2;w if(Ri.key=high+1;j-)dj+1=dj;移动元素移动元素w dhigh+1=Ri;final+;插入有序位置插入有序位置w 19 else if(first=1)插入前部插入前部w first=n;dn=Ri;w else low=first;high=n;w while(low=high)w m=(low+high)/2;w if(Ri.k
15、ey dm.key)high=m-1;w else low=m+1;w whilew for(j=first;j=high;j+)dj-1=dj;w 移动元素移动元素w dhigh=Ri;first-;w ifw if w /for w 20表插入排序表插入排序w 静态链表静态链表w#define n 待排序记录的个数待排序记录的个数w typedef structw int key;w AnyType other;记录其他数据域记录其他数据域w int next;w STListType;w STListType SLn+1;21表插入排序算法表插入排序算法w void ListInsSor
16、t(STListType SL,int n)w 对记录序列对记录序列SL1.n作表插入排序。作表插入排序。w SL0.key=MAXINT;w SL0.next=1;SL1.next=0;w for(i=2;i=n;i+)查找插入位置查找插入位置w j=0;w for(k=SL0.next;SLk.key=SLi.key;)w j=k,k=SLk.next;w SLj.next=i;SLi.next=k;w 结点结点i插入在结点插入在结点j和结点和结点k之间之间w for w ListInsSort22表物理排序表物理排序w void Arrange(STListType SL,int n)w
17、 调整静态链表调整静态链表SL中各结点的指针值,使记录按关键字有序排列中各结点的指针值,使记录按关键字有序排列w p=SL0.next;p指示第一个记录的当前位置指示第一个记录的当前位置w for(i=1;in;i+)w SL1.i-1 记录已按关键字有序,第记录已按关键字有序,第i个记录的当前位置应不小于个记录的当前位置应不小于iw while(p=1;d=d/2)for(i=1+d;i0&R0.keyaj+1),则将其交),则将其交换,最终达到有序化换,最终达到有序化 29起泡排序示例初始关键字序列:初始关键字序列:51 33 62 96 87 17 28 51第一趟排序结果:第一趟排序结
18、果:33 51 62 87 17 28 51 96 第二趟排序结果:第二趟排序结果:33 51 62 17 28 51 87 96 第三趟排序结果:第三趟排序结果:33 51 17 28 51 62 87 96 第四趟排序结果:第四趟排序结果:33 17 28 51 51 62 87 96 第五趟排序结果:第五趟排序结果:17 28 33 51 51 62 87 96 第六趟排序结果:第六趟排序结果:17 28 33 51 51 62 87 96 30void BubbleSort(RecType R,int n)起泡排序起泡排序 i=n;i 指示无序序列中最后一个记录的位置指示无序序列中最后
19、一个记录的位置 while(i1)lastExchange=1;记最后一次交换发生的位置记最后一次交换发生的位置 for(j=1;jRj+1.key)temp=Rj;Rj=Rj+1;Rj+1=temp;逆序时交换逆序时交换 lastExchange=j;if i=lastExchange;while 起泡排序算法31一组关键字一组关键字(19,01,26,92,87,11,43,87,2119,01,26,92,87,11,43,87,21),),进行冒泡排序,进行冒泡排序,试列出每一趟排序后的关键字序列试列出每一趟排序后的关键字序列 32快速排序 n基本思想基本思想:从待排序记录序列中任选取
20、一:从待排序记录序列中任选取一个记录(通常可选第一个记录)的关键字个记录(通常可选第一个记录)的关键字作为作为枢轴枢轴(或支点),凡其关键字小于枢(或支点),凡其关键字小于枢轴的记录均移动至该记录之前,而关键字轴的记录均移动至该记录之前,而关键字大于枢轴的记录均移动至该记录之后。一大于枢轴的记录均移动至该记录之后。一趟快速排序后就将排序序列分成两部分,趟快速排序后就将排序序列分成两部分,再分别对这两部分再分别对这两部分递归递归快速排序。快速排序。由由Hoare(图灵奖获得者图灵奖获得者)1962年提出,被评年提出,被评为为20世纪十大优秀算法之一世纪十大优秀算法之一。33快速排序图示1n34快
21、速排序示例初始关键字序列初始关键字序列:51 33 62 96 87 17 28 51R0=51 i(枢轴枢轴)jj向前扫描向前扫描 i j第一次交换之后:第一次交换之后:28 33 62 96 87 17 51 i ji向后扫描向后扫描 i j第二次交换之后:第二次交换之后:28 33 96 87 17 62 51 i jj向前扫描向前扫描 i j 第三次交换之后:第三次交换之后:28 33 17 96 87 62 51i向后扫描向后扫描 i j 第四次交换之后:第四次交换之后:28 33 17 87 96 62 51j向前扫描向前扫描 i j 完成一趟排序:完成一趟排序:28 33 17
22、51 87 96 62 51 ij 35快速排序示例初始关键字序列初始关键字序列:51 33 62 96 87 17 28 51一趟排序之后一趟排序之后:28 33 17 51 87 96 62 51 分别进行快速排序:分别进行快速排序:17 28 33 结束结束 结束结束 51 62 87 96 51 62 结束结束 结束结束有序序列:有序序列:17 28 33 51 51 62 87 9636快速排序算法int Partition(RecType R,int l,int h)交换记录子序列交换记录子序列Rl.h中的记录,使枢轴记录到位并返回其所在位置中的记录,使枢轴记录到位并返回其所在位置
23、 int i=l;j=h;用变量用变量i,j记录待排序记录首尾位置记录待排序记录首尾位置 R0=Ri;以子表的第一个记录作枢轴,将其暂存到记录以子表的第一个记录作枢轴,将其暂存到记录R0中中 x=Ri.key;用变量用变量x存放枢轴记录的关键字存放枢轴记录的关键字 while(ij)从表的两端交替地向中间扫描从表的两端交替地向中间扫描 while(i=x)j-;Ri=Rj;将比枢轴小的记录移到低端将比枢轴小的记录移到低端 while(ij&Ri.key=x)i+;Rj=Ri;将比枢轴大的记录移到高端将比枢轴大的记录移到高端 while Ri=R0;枢轴记录到位枢轴记录到位 return i;返
24、回枢轴位置返回枢轴位置Partition 37快速排序算法void QuickSort(RecType R,int s,int t)对记录序列对记录序列Rs.t进行快速排序进行快速排序 if(st)k=Partition(R,s,t);QuickSort(R,s,k-1);QuickSort(R,k+1,t);if QuickSort 快速排序的快速排序的平均时间复杂度平均时间复杂度为为O(nlog2n)最差为最差为O(n2)38对下列一组关键字对下列一组关键字(46,58,15,45,90,18,10,6246,58,15,45,90,18,10,62)试写出快速排序的每一趟的排序结果试写出
25、快速排序的每一趟的排序结果 39选择排序 基本思想基本思想:依次从待排序记录序列中选择出关键:依次从待排序记录序列中选择出关键字值最小(或最大)的记录、关键字值次之的字值最小(或最大)的记录、关键字值次之的记录、记录、,并分别将它们定位到序列左侧,并分别将它们定位到序列左侧(或右侧)的第(或右侧)的第1个位置、第个位置、第2 2个位置、个位置、,从而使待排序的记录序列成为按关键字值由小从而使待排序的记录序列成为按关键字值由小到大(或由大到小)排列的有序序列。到大(或由大到小)排列的有序序列。选择排序种类选择排序种类:直接(简单)选择排序直接(简单)选择排序 树形选择排序树形选择排序 堆排序堆排
展开阅读全文