自考数据结构02142-第七章ppt课件.ppt

《自考数据结构02142-第七章ppt课件.ppt》由会员分享，可在线阅读，更多相关《自考数据结构02142-第七章ppt课件.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第第七七章章 排序排序7 7.1.1 概述概述7 7.2.2 插入排序插入排序7 7.3.3 交换排序交换排序7 7.4.4 选择排序选择排序7.5 7.5 归并排序归并排序在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确数据排序数据排序将一个文件的记录按关键字不减（将一个文件的记录按关键字不减（或不增）次序排列，使文件成为有序文件，此过或不增）次序排列，使文件成为有序文件，此过 程称为排序。程称为排序。稳定排序稳定排序若排序后

2、，若排序后，相同相同关键字的记录保持关键字的记录保持 它们原来的相对次序，则此排序方法称为。它们原来的相对次序，则此排序方法称为。不稳定排序不稳定排序排序类型排序类型内部排序：内部排序：全部数据存于内存；全部数据存于内存；外部排序外部排序:需要对外村进行访问的需要对外村进行访问的排序过程排序过程7.1 7.1 概述概述在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确内部排序内部排序按方法分按方法分插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度

3、，由浅入深，所提出的问题也很明确排序文件的物理表示：排序文件的物理表示：数组表示数组表示排序指标（排序算法分析）：排序指标（排序算法分析）：存储空间存储空间-空间复杂度空间复杂度 比较次数比较次数-时间复杂度时间复杂度#define n 100#define n 100/*/*序列中待排序记录的总数序列中待排序记录的总数*/*/typedef structtypedef struct int key;int key;/*/*关键字项关键字项*/*/anytype otheritem;anytype otheritem;/*/*其他数据项其他数据项*/*/records;records;type

4、def records listn+1;typedef records listn+1;list r;list r;r0 r1 r2.rnr0 r1 r2.rnri.keyri.key第第i i个记录的关键字个记录的关键字在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1.1.过程：过程：对对R R1 1，R Ri-1i-1已排好序，有已排好序，有K K1 1KK2 2.K.Ki-1i-1，现将现将K Ki i依次与依次与K Ki-1i-1，K Ki-2i-2，进行比较，并移动元进行比较，并移动元素，素，直到发现直到发现R Ri i应

5、插在应插在R Rj j与与R Rj+1j+1之间之间(即有即有K Kj jKKi iK Kj+1j+1 )，则将则将R Ri i插到插到j+1j+1号位置上，形成号位置上，形成i i个有序序列。个有序序列。（i i从从2 2n n）2.2.算法：算法：见见P1853.3.例例：见见P1864.4.算法分析：算法分析：空间复杂度空间复杂度O(1):O(1):需要一个辅助空间需要一个辅助空间 时间复杂度时间复杂度 O(nO(n2 2)稳定性：稳定性：稳定排序稳定排序；直接插入排序直接插入排序7.2 7.2 插入排序（通过比较插入实现排序）插入排序（通过比较插入实现排序）在整堂课的教学中，刘教师总是

6、让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确直接插入排序算法：直接插入排序算法：void void S StraighttraightInsertInsertsort(list rsort(list r,int n,int n););/*/*用直接插入排序法对用直接插入排序法对r1rnr1rn进行排序进行排序*/*/int i,j;int i,j;for(ifor(i=2;i=n;i+)2;i=n;i+)r0=ri;r0=ri;j=i-1;j=i-1;while(r0.keyrj.key)while(r0.keyrj.key)rj+1=rj;rj+1=rj;

7、/*/*记录后移记录后移*/*/j=j-1;j=j-1;rj+1=r0;rj+1=r0;/*/*插入插入*/*/在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确7.3 7.3 交换排序（通过比较交换实现排序）交换排序（通过比较交换实现排序）一、冒泡排序一、冒泡排序1.1.基本思想：基本思想：通过多次重复比较、交换相邻记录而实通过多次重复比较、交换相邻记录而实 现排序；每一趟的效果都是将当前键值最大的记录现排序；每一趟的效果都是将当前键值最大的记录 换到最后换到最后。（见（见P P187187）2.2.例：例：试对下列待排序序列用冒泡排

8、序法进行排序试对下列待排序序列用冒泡排序法进行排序,给出每趟结给出每趟结果果:49，38，65，97，76，134，27，49第一趟：第一趟：38496576972749134第二趟：第二趟：38496576274997134第三趟：第三趟：38496527497697134第四趟：第四趟：38492749657697134第五趟：第五趟：38274949657697134第六趟：第六趟：27384949657697134第七趟：第七趟：27384949657697134在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.3.冒泡排序

9、冒泡排序算法：算法：见下页。见下页。4.4.算法分析：算法分析：时间复杂度：外循环最多时间复杂度：外循环最多n-1n-1次（最少次（最少1 1次），次），第第i i次外循环时，内循环次外循环时，内循环n-in-i次比较，次比较，最大比较次数为最大比较次数为n ni=1i=1n-i=n(n-1)/2nn-i=n(n-1)/2n2 2/2 /2 =O(nO(n2 2)稳定性：稳定性：稳定排序稳定排序。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确冒泡排序算法：冒泡排序算法：Void bubbleSort(list r,int n)Voi

10、d bubbleSort(list r,int n)int i,j,temp,endsort;int i,j,temp,endsort;for(i=1;i=for(i=1;i=n-1n-1;i+);i+)endsort=0endsort=0;for(j=1;j=n-i for(j=1;j rj rj+1+1.key).key)temp=rj;temp=rj;rj=rj+1;rj=rj+1;rj+1=rj+1=temptemp;endsort=1endsort=1;if(if(endsort=0endsort=0)breakbreak;在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设

11、置具有一定的梯度，由浅入深，所提出的问题也很明确 首先取第一个记录，将之与表中其余记录比较并交换，从而将首先取第一个记录，将之与表中其余记录比较并交换，从而将它放到记录的正确的最终位置，使记录表分成两部分它放到记录的正确的最终位置，使记录表分成两部分 其一（左边的）其一（左边的）诸记录的关键字均小于它；其二（右边的）诸记录的关键字均大于它诸记录的关键字均小于它；其二（右边的）诸记录的关键字均大于它；然后对这两部分重新执行上述过程，依此类推，直至排序完毕。；然后对这两部分重新执行上述过程，依此类推，直至排序完毕。二、快速排序二、快速排序1.1.基本思想：基本思想：通过分部排序完成整个表的排通过分

12、部排序完成整个表的排序；序；2.2.过程：过程：记录序列记录序列 r rlowlow,rlow+1,r,rlow+1,rhighhigh 设：左指针设：左指针i i，右指针，右指针j;j;初值：初值：i=i=lowlow；j=j=highhigh;处理元素处理元素=x;=x;初始时：初始时：r1=xr1=x在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确(2)(2)i i指针逐步右移，即：指针逐步右移，即：将将riri与与x x比较，比较，i i不断增不断增1 1，直到发现某个，直到发现某个 ri.key ri.keyx.keyx.k

13、ey时，则：时，则：ri=j ri=j位置上；位置上；j-1=j;j-1=j;转转(1);(1);此过程直到此过程直到(1)(1)或或(2)(2)中中i=ji=j时停止，此时将处时停止，此时将处理元素理元素x x送到送到i i或或j j位置上，它将原序列分成左、位置上，它将原序列分成左、右两个子序列，对它们分别进行上述过程，直右两个子序列，对它们分别进行上述过程，直至分裂后的子序列都只有一个元素为止。至分裂后的子序列都只有一个元素为止。(1)(1)j j指针逐步左移指针逐步左移，即：，即：将将rjrj与与x x比较，比较，j j不断减不断减1 1，直到发现某个，直到发现某个 rj.keyx.k

14、eyrj.keyi rj=i位置上（开始时位置上（开始时i=1i=1）；）；i+1=i;i+1=i;转转(2)(2)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确4.4.算法：算法：P189P189。5.5.算法分析：算法分析：平均平均时间时间性能性能：O(nlogO(nlog2 2n)n);注：若初始记录表有序或基本有序，则快速排序将注：若初始记录表有序或基本有序，则快速排序将 蜕化为冒泡排序蜕化为冒泡排序,其时间复杂度为其时间复杂度为O(nO(n2 2)；即：即：快速排序在表基本有序时，最不利于其发挥效率。快速排序在表基本有序时

15、，最不利于其发挥效率。稳定性：稳定性：不稳定排序不稳定排序。第一趟：第一趟：36，55,48，37，106084，90第二趟：第二趟：103648，37,55608490第三趟：第三趟：1036374855608490结结果：果：1036374855608490 3.3.例：例：试对下列待排序序列用快速排序法进行排序试对下列待排序序列用快速排序法进行排序,给出每趟结给出每趟结果果:60，55，48，37，10，90，84，36 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确7.47.4 选择排序选择排序（以重复选择的思想为基础进行排

16、序）（以重复选择的思想为基础进行排序）一、直接选择排序一、直接选择排序1.1.过程：过程：设记录设记录R R1 1，R R2 2，R Rn n，对对i=1i=1，2 2，n-1n-1，重复下列工作：，重复下列工作：(1)(1)在在R Ri i，R Rn n中选最小中选最小(或最大或最大)关键字记录关键字记录R Rj j；(2)(2)将将R Rj j与第与第i i个记录交换位置，即将选到的第个记录交换位置，即将选到的第i i 小的记录换到第小的记录换到第i i号位置上。号位置上。2.2.例：例：试对下列待排序序列用选择排序法进行排序试对下列待排序序列用选择排序法进行排序,给出每趟结给出每趟结果果

17、:46，15，13，94，17第一趟：第一趟：1315，46，94，17第二趟：第二趟：1315 46，94，17第三趟：第三趟：13151794，46第四趟：第四趟：1315174694在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.3.算法：算法：直接选择排序直接选择排序 4.4.算法分析算法分析:时间：时间：C C总总=n ni=1i=1(n-i)=(n(n-i)=(n2 21)/21)/2O(nO(n2 2)稳定性：稳定性：不稳定排序不稳定排序；（P191）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有

18、一定的梯度，由浅入深，所提出的问题也很明确二、堆排序二、堆排序1.1.堆：堆：集合集合 K K1 1,K,K2 2,.,K,.,Kn n ，对所有对所有i=1,2,n/2 i=1,2,n/2 有：有：K Ki iKK2i2i 且且 K Ki iKK2i+12i+1，则此集合称为则此集合称为堆堆（最小堆）（最小堆）;（或（或K Ki iKK2i2i 且且K Ki iKK2i+12i+1 最大堆）最大堆）例例：13,40,27,88,55,34,65,9213,40,27,88,55,34,65,92(最小最小堆堆)92,65,88,40,55,34,13,2792,65,88,40,55,34,

19、13,27(最大最大堆堆)下标下标：1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确堆堆 K K1 1,K,K2 2,.,K,.,Kn n 概念上概念上 可看成可看成顺序存储的完全二叉树顺序存储的完全二叉树（R Ri i对应结点对应结点i i）且且树中双亲关键字值均不超过孩子的关键字树中双亲关键字值均不超过孩子的关键字；注：注：堆根最小；堆根最小；输出根结点输出根结点剩下的再构造堆剩下的再构造堆直到最后一结点直到最后一结点堆排序思想堆排序思想在整堂课的教学中，刘教师总是让学

20、生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2.2.建堆（筛选法）：建堆（筛选法）：1 1）方法：）方法：设记录设记录 R R1 1,R,R2 2,.,R,.,Rn n (1)(1)顺序输入成完全二叉树（以数组存顺序输入成完全二叉树（以数组存储）储）(2)(2)从从最后一个双亲最后一个双亲开始，如果有较小开始，如果有较小的的 孩子，则将其沿左或右孩中孩子，则将其沿左或右孩中小小的那的那个个 方向筛下，一直到不能再筛；方向筛下，一直到不能再筛；(3)(3)逐次处理完每个双亲。逐次处理完每个双亲。2 2）例子：）例子：（见下页）；（见下页）；3 3）算法：）算法：下

21、筛一个结点算法下筛一个结点算法(见见P195)P195)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确例：判别下列序列是否为堆，如果不是则将例：判别下列序列是否为堆，如果不是则将之调之调整为堆。整为堆。12,70,53,65,24,56,48,92,86,3312,70,53,65,24,56,48,92,86,3312705348566524928633不是堆不是堆127048535665249286337065且且7024244853沿右筛下沿右筛下12244853566570928633703370沿左筛下沿左筛下122448

22、53566533928670在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.3.堆排序：堆排序：1 1）过程：）过程：从从i=int(n/2i=int(n/2）1 1 调用调用sift(r,i,n)sift(r,i,n)建初始堆建初始堆 对对i=n,n-1,n-2,.,2i=n,n-1,n-2,.,2重复重复、输出输出r1,r1,即：即：r1 r1 ri ri 调用调用sift(r,1,i-1),sift(r,1,i-1),重新建堆重新建堆 2 2）算法算法:3 3）例：）例：（见下页）（见下页）4.4.算法分析：算法分析：空间：

23、空间：n+1n+1；（仅需（仅需1 1个附加空间）个附加空间）时间：时间：O O（nlogn)O(nnlogn)O(n2 2)稳定性：不稳定排序；稳定性：不稳定排序；在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确例：对下列序列进行堆排序。例：对下列序列进行堆排序。12,70,53,65,24,56,48,92,86,3312,70,53,65,24,56,48,92,86,3312244853566533928670初始初始堆堆输出输出1270244853566533928612下筛下筛70重建堆重建堆243348535665709

24、28612输出输出2486334853566570922412在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确下筛下筛86重建堆重建堆33654853568670922412输出输出3392654853568670332412下筛下筛92重建堆重建堆48655392568670332412输出输出4892655348568670332412下筛下筛92重建堆重建堆53655648928670332412输出输出5392655648538670332412在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅

25、入深，所提出的问题也很明确下筛下筛92重建堆重建堆56659248538670332412输出输出5670659248538656332412下筛下筛70重建堆重建堆65709248538656332412输出输出6586709248536556332412下筛下筛86重建堆重建堆70869248536556332412输出输出7092867048536556332412在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确下筛下筛92重建堆重建堆86927048536556332412输出输出7092867048536556332412在

26、整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确7.5 7.5 归并排序归并排序1.1.思想：思想：比较各个子序列的第一个记录的键比较各个子序列的第一个记录的键值，最小的一个就是排序后序列的第一个记值，最小的一个就是排序后序列的第一个记录。取出这个记录，继续比较各子序列现有录。取出这个记录，继续比较各子序列现有的第一个记录的键值，便可找出排序后的第的第一个记录的键值，便可找出排序后的第二个记录。如此继续下去，最终可以得到排二个记录。如此继续下去，最终可以得到排序结果。序结果。2.2.两个有序表归并算法两个有序表归并算法 （见（见P199

27、P199）一、有序序列的合并一、有序序列的合并(两个有序表归并成一个有两个有序表归并成一个有序表序表)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 两两归并成两两归并成 n/2 n/2 个，长度为个，长度为2 2的有序表（的有序表（n n为奇数，则为奇数，则 还有还有1 1个长为个长为1 1的表）的表）二、归并排序二、归并排序1.1.思想：思想：（2-2-路归并排序路归并排序）n n个记录的表看成个记录的表看成n n个，长度为个，长度为1 1的有序表的有序表再两两归并为再两两归并为 n/2/2 n/2/2 个，长度为个，长度为4

28、4的有序表的有序表 .再两两归并直至只剩再两两归并直至只剩1 1个，长度为个，长度为n n的有序表；的有序表；共共loglog2 2n n趟趟在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2.2.例：例：3.2-3.2-路归并算法：路归并算法：(见见P200算法算法)4.4.算法分析：算法分析：空间：空间：n+nn+n；（需（需n n个附加空间）个附加空间）时间：时间：O O（nlogn)nlogn)稳定性：稳定排序；稳定性：稳定排序；第一趟：第一趟：137475219481382674326350506815第二趟：第二趟：137

29、219475481326350382674506815第三趟：第三趟：137219326350382475481674506815第四趟：第四趟：137219326350382475481506674815试对下列待排序序列用归并排序法进行排序试对下列待排序序列用归并排序法进行排序,给出每趟结果给出每趟结果:475，137，481，219，382，674，350，326，815，506在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确7.6 7.6 各种排序方法的比较各种排序方法的比较在整堂课的教学中，刘教师总是让学生带着问题来学习，而

30、问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 掌掌握握各各种种排排序序算算法法思思想想、排排序序过过程程、稳定性及算法的时间复杂性。稳定性及算法的时间复杂性。重点：重点：各种排序方法的过程。各种排序方法的过程。第第七七章章排排序序小小结结在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1排序是根据什么的大小重新安排各元素的顺序？（排序是根据什么的大小重新安排各元素的顺序？（）A数组数组B关键字关键字C元素元素D结点结点2快速排序在最坏的情况下的时间复杂度是快速排序在最坏的情况下的时间复杂度是()AO(log2n)B.O(n

31、log2n)C.O(n)D.O(n2)3以下四种排序方法中，要求附加空间最大的是（以下四种排序方法中，要求附加空间最大的是（）A.插入排序插入排序B.冒泡排序冒泡排序C.归并排序归并排序D.快速排序快速排序4快速排序的方法是（快速排序的方法是（）A稳定排序稳定排序B.不稳定排序不稳定排序C.外部排序外部排序D.选择排序选择排序5冒泡排序的方法是（冒泡排序的方法是（）A稳定排序稳定排序B.不稳定排序不稳定排序C.外部排序外部排序D.选择排序选择排序练练习习在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确6以下时间复杂度不是以下时间复杂度不是O(n2)的排序方法是（的排序方法是（）A.直接插入排序直接插入排序B.冒泡排序冒泡排序C.快速排序快速排序D.直接选择排序直接选择排序