数据结构课件排序ppt.ppt

《数据结构课件排序ppt.ppt》由会员分享，可在线阅读，更多相关《数据结构课件排序ppt.ppt（69页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第第10章章 内部排序内部排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 选择排序选择排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种内部排序方法的比较讨论各种内部排序方法的比较讨论1在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确10.1概述概述排序排序 是将数据元素的一个任意序列，重新排列成一是将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。个按关键字有序

2、的序列。排序的一个确切定义：排序的一个确切定义：假设含假设含n个记录的序列为个记录的序列为 R1,R2,R3,Rn其相应的关键字序列为其相应的关键字序列为K1,K2,Kn需确定需确定1,2,n的一种排列的一种排列P1,P2,P3,Pn,使其相应的关使其相应的关键字满足如下的递增键字满足如下的递增(或递减或递减)关系关系:Kp1Kp2Kpn即使序列即使序列R1,R2,R3,Rn成为一个按关键字有序的序列成为一个按关键字有序的序列:Rp1,Rp2,Rp3,Rpn这种操作称为排序这种操作称为排序.2在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也

3、很明确稳定排序方法稳定排序方法假设假设Ki=Kj(1=i,j=n,ij),且在排序前的序且在排序前的序列中列中Ri领先于领先于Rj，若在排序后的序列中，若在排序后的序列中Ri仍仍领先领先Rj，则称所用的排序方法是，则称所用的排序方法是稳定的稳定的。不稳定排序方法不稳定排序方法假设假设Ki=Kj(1=i,j=n,ij),且在排序前的序列且在排序前的序列中中Ri领先于领先于Rj，若在排序后的序列中，若在排序后的序列中Rj领先领先Ri，则称所用的排序方法是，则称所用的排序方法是不稳定的不稳定的。例：例：姓名姓名年龄年龄体重体重1李由李由57622王天王天54763七明七明24754张强张强24725

4、陈华陈华2453按某种按某种稳定稳定方法对年龄方法对年龄关键字进行关键字进行排序排序姓名姓名年龄年龄体重体重3七明七明24754张强张强24725陈华陈华24532王天王天54761李由李由57623在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确姓名姓名年龄年龄体重体重1李由李由57622王天王天54763七明七明24754张强张强24725陈华陈华2453按某种按某种不稳不稳定定方法对年方法对年龄关键字进龄关键字进行排序行排序姓名姓名年龄年龄体重体重4张强张强24723七明七明24755陈华陈华24532王天王天54761李由李由

5、5762待排序记录存放在计算机随机存储器中进待排序记录存放在计算机随机存储器中进行的排序过程；行的排序过程；内部排序内部排序待排序记录的数量很大，以致内存一次不待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程；存进行访问的排序过程；外部排序外部排序4在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确按排序过程中依据的不同原则对内排方法分类：按排序过程中依据的不同原则对内排方法分类：（1）插入排序）插入排序（2）交换排序）交换排序（3）选择排序）选择排序（4）

6、归并排序）归并排序（5）基数排序）基数排序按内排过程中所需的工作量分类：按内排过程中所需的工作量分类：（1）简单的排序方法，其时间复杂度为）简单的排序方法，其时间复杂度为O(nn)（2）先进的排序方法，其时间复杂度为）先进的排序方法，其时间复杂度为O(nlogn);（3）基数排序，其时间复杂度为）基数排序，其时间复杂度为O(dn)排序算法的两种基本操作：排序算法的两种基本操作：（1）比较比较两个关键字的大小；两个关键字的大小；（2）将记录从一个位置）将记录从一个位置移移至另一个位置；至另一个位置；5在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的

7、问题也很明确待排序的记录序列可有三种存储方式：待排序的记录序列可有三种存储方式：（1）待排序的记录存放在地址连续的一组存储单元上。）待排序的记录存放在地址连续的一组存储单元上。（2）待排序的记录存放在静态链表中。）待排序的记录存放在静态链表中。（3）待排序的记录本身存储在一组地址连续的存储单元）待排序的记录本身存储在一组地址连续的存储单元 内内,同时另设一个指示各个记录存储位置的地址向量。同时另设一个指示各个记录存储位置的地址向量。待排序记录的数据类型设为：待排序记录的数据类型设为：P2646在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也

8、很明确10.2插入排序插入排序插入排序插入排序直接插入排序直接插入排序折半插入排序折半插入排序2-路插入排序路插入排序表插入排序表插入排序希尔排序希尔排序10.2.1直接插入排序直接插入排序直接插入排序的基本操作是将一个记录插入到已排好序的直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增有序表中，从而得到一个新的、记录数增1的有序表。的有序表。例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)用用L(sqlist L)的的L.r1.key.L.r8.key依次存储依次存储L

9、.r1.key.L.r8.key是是递增有序的递增有序的直接插直接插入排序入排序7在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确直接插入排序的过程直接插入排序的过程:初始关键字初始关键字r0 r1 r2 r3 r4 r5 r6 r7 r8 49 38 65 97 76 13 27 49第一趟插入第一趟插入384965 97 76 13 27 49第二趟插入第二趟插入38496597 76 13 27 49第三趟插入第三趟插入38 49 65 97 76 13 27 49第四趟插入第四趟插入38 49 65 76 9713 27 49

10、第五趟插入第五趟插入13 38 49 65 76 9727 49第六趟插入第六趟插入13 27 38 49 65 76 9749第七趟插入第七趟插入13 27 38 49 49 65 76 97i=2i=3i=4i=5i=6i=7i=88在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确直接插入排序算法分析直接插入排序算法分析:有有n个记录待排序个记录待排序,需进行需进行2.n共共n-1趟插入趟插入;一级算一级算法：法：Void insertsort(sqlist&L)for (i=2;i=L.length;+i)第第i趟插入；趟插入；

11、第第i趟插入完成的功能趟插入完成的功能:在含有在含有i-1个记录的有序序列个记录的有序序列r1.i-1 中插入一个记录中插入一个记录ri,插入后变成含插入后变成含 有有i个记录的有序序列个记录的有序序列r1.i。9在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第第i趟插入的算法趟插入的算法二级算二级算法：法：例：第例：第i=7趟插入：趟插入：if (LT(L.ri.key,L.ri-1.key)L.ri插入到插入到 L.r1.L.ri-1中中 L.r0=L.ri;L.ri=L.ri-1;For (j=i-2;LT(L.r0.key,

12、L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;13 38 49 65 76 97 27 491 2 3 4 5 6 7 810在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确三级算三级算法：法：Void insertsort(sqlist&L)for (i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.ri=L.ri-1;For (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;11

13、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确直接插入排序的性能分析直接插入排序的性能分析:(1)空间空间:只需一个记录的辅助空间只需一个记录的辅助空间r0.(2)时间时间:基本运算基本运算:比较和移动记录比较和移动记录;比较和移动记录的次数与关键字的初始序列有关比较和移动记录的次数与关键字的初始序列有关:(1)待排序序列关键字正序排序待排序序列关键字正序排序:关键字比较次数关键字比较次数:n-1 移动记录的次数移动记录的次数:0(2)待排序序列关键字逆序排序待排序序列关键字逆序排序:关键字比较次数关键字比较次数:2+3+n=(n+

14、2)(n-1)/2 移动记录的次数移动记录的次数:3+4+5+(n+1)=(n+4)(n-1)/2(3)待排序序列关键字随机排序待排序序列关键字随机排序:关键字比较次数关键字比较次数:(n-1)(n+4)/4 移动记录的次数移动记录的次数:(n+4)(n-1)/4直接插入排序算直接插入排序算法的时间复杂度法的时间复杂度为为O(nn)12在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确10.2.2 其它插入排序其它插入排序折半插入排序折半插入排序:把直接插入算法中对插入位置的搜索从把直接插入算法中对插入位置的搜索从顺序搜索顺序搜索改进为

15、改进为折半搜索折半搜索.Void Binsertsort(sqlist&L)for (i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.ri=L.ri-1;For (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;P267算法算法10.213在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确折半插入排序的性能分析折半插入排序的性能分析:(1)空间空间:只需一个记录的辅助空间只需一个记录的辅助空间r0;(2)时间时

16、间:基本运算基本运算:比较和移动记录比较和移动记录;折半插入排序算法的时间复杂度为折半插入排序算法的时间复杂度为O(nn)14在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2-路插入排序路插入排序为减少排序过程中移动记录的次数，在折半插入排序的为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：基础上加以改进：例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)另设一个和另设一个和r同类型的数组同类型的数组d,首先将首先将r1赋值给赋值给d

17、1,并将并将d1看成看成是在排好序的序列中处于中间位置的记录是在排好序的序列中处于中间位置的记录,然后从然后从r中第中第2个记录起个记录起依次插入到依次插入到d1之前或之后的有序序列中之前或之后的有序序列中.先将待插记录的关键字和先将待插记录的关键字和d1的关键字进行比较的关键字进行比较.若若ri.keyd1.key,则将则将ri插入到插入到d1之前之前的有序表中的有序表中,反之反之,则将则将ri插入到插入到d1之后的有序表中之后的有序表中.算法实现的关键设计算法实现的关键设计:将将d看成是一个循环数组看成是一个循环数组,并设两个指针并设两个指针first和和final分别指示排序过分别指示排

18、序过程中得到的有序序列中的第一个记录和最后一个记录在程中得到的有序序列中的第一个记录和最后一个记录在d中的位置中的位置.15在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 d1 d2 d3 d4 d5 d6 d7 d8 初始关键字初始关键字49 38 65 97 76 13 27 49i=1:49first finali=2:4938firstfinali=3:493865finalfirsti=4:49386597finalfirsti=5:4938657697finalfirsti=6:493865769713finalfirs

19、ti=7:49386576971327finalfirsti=8:4949657697132738finalfirst16在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2-路插入排序的性能分析路插入排序的性能分析:(1)空间空间:(2)时间时间:基本运算基本运算:比较和移动记录比较和移动记录;2-路插入排序算法的时间复杂度为路插入排序算法的时间复杂度为O(nn)17在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确10.2.3希尔排序希尔排序从直接插入排序从直接插入排序待排序

20、序列基本有序可提高效率待排序序列基本有序可提高效率待排序序列的记录数待排序序列的记录数n很小时可提高效率很小时可提高效率希尔排序的基本思想希尔排序的基本思想:先将整个待排记录序列分割成为若干子序列分别进行先将整个待排记录序列分割成为若干子序列分别进行直接插入排序直接插入排序,待整个序列中的记录待整个序列中的记录“基本有序基本有序”时时,再对再对全全体记录进行一次直接插入排序体记录进行一次直接插入排序.例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)18在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的

21、设置具有一定的梯度，由浅入深，所提出的问题也很明确初始关键字初始关键字r0 r1 r2 r3 r4 r5 r6 r7 r8 49 38 65 97 76 13 27 49第一趟排序后第一趟排序后:(d1=3)27 38 13 49 49 65 97 76第二趟排序后第二趟排序后:(d2=2)13 27 49 97第三趟排序后第三趟排序后:(d3=1)13 27 38 49 49 65 76 97 38 49 65 7619在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确希尔排序算法的实现希尔排序算法的实现:Void shellsort

22、(sqlist&L,int dlta,int t)for (i=0;it;+i)以以dltai为增量的一趟排序；为增量的一趟排序；Shellinsert（sqlist&L,dltai);Void insertsort(sqlist&L)for (i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.ri=L.ri-1;For (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;(1)记录的增量记录的增量为为dk;(2)r0不是哨不是哨兵。兵。j=0，插，插入位置已找到。入位置

23、已找到。P272算法算法10.420在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确希尔排序的性能分析：希尔排序的性能分析：(1)空间空间:只需一个记录的辅助空间只需一个记录的辅助空间r0;(2)时间时间:基本运算基本运算:比较和移动记录比较和移动记录;时间复杂度为：时间复杂度为：O（n3/2）增量的取法应注意：使增量序列中的值没有除增量的取法应注意：使增量序列中的值没有除1之外的公之外的公 因子，并且最后一个增量值必须为因子，并且最后一个增量值必须为1。21在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度

24、，由浅入深，所提出的问题也很明确10.3快速排序快速排序起泡排序的基本思想起泡排序的基本思想:首先将第一个记录的关键字和第二个记录的关键字进首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第个记录和第三个记录的关键字。直至第n-1个记录和第个记录和第n个个记录的关键字进行过比较为止。记录的关键字进行过比较为止。然后进行第二趟起泡排序，对前然后进行第二趟起泡排序，对前n-1个记录进行同样操作。个记录进行同样操作。结束的条件结束的条件:(1)趟数为趟数为n-1;(2)直

25、到在某趟排序过程中没有直到在某趟排序过程中没有进行过交换进行过交换记录的操作为止。记录的操作为止。22在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)第一趟第一趟:4938659776132749384965977613274938496597761327493849659776132749384965769713274938496576139727493849657613279749384965761

26、3274997第一趟进行第一趟进行7次比较次比较23在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确49386597761327493849657613274997初初始始关关键键字字第第一一趟趟排排序序后后38496513274976第第二二趟趟排排序序后后384913274965第第三三趟趟排排序序后后3813274949第第四四趟趟排排序序后后13273849第第五五趟趟排排序序后后132738第第六六趟趟排排序序后后1327第第七七趟趟排排序序后后整整个个排排序序过过程程24在整堂课的教学中，刘教师总是让学生带着问题来学习，而

27、问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确起泡排序算法的性能分析起泡排序算法的性能分析:(1)空间空间:只需一个记录的辅助空间只需一个记录的辅助空间.(2)时间时间:基本运算基本运算:比较和移动记录比较和移动记录;比较和移动记录的次数与关键字的初始序列有关比较和移动记录的次数与关键字的初始序列有关:(1)待排序序列关键字正序排序待排序序列关键字正序排序:关键字比较次数关键字比较次数:n-1 移动记录的次数移动记录的次数:0(2)待排序序列关键字逆序排序待排序序列关键字逆序排序:关键字比较次数关键字比较次数:(n-1)+(n-2)+1=n(n-1)/2 移动记录的次数移动记录的次数

28、:3n(n-1)/2(3)待排序序列关键字随机排序待排序序列关键字随机排序:关键字比较次数关键字比较次数:(n-1)(n+2)/4 移动记录的次数移动记录的次数:3n(n-1)/4起泡排序算法的起泡排序算法的时间复杂度为时间复杂度为O(nn)25在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确快速排序的基本思想快速排序的基本思想:通过一趟排序将待排记录分割成独立的两部分，其中一部分记通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录的关键字均比另一部分记录的关键字小，则可

29、分别对这两部分记录继续进行排序，以达到整个序列有序。录继续进行排序，以达到整个序列有序。算法实现分析：算法实现分析：（1）假设待排序的序列为）假设待排序的序列为L.rs,L.rs+1,L.rt；（2）任意选取一个记录作为枢轴，然后重新排列其余记录，将所）任意选取一个记录作为枢轴，然后重新排列其余记录，将所 有关键字较它小的记录都安置在它的位置之前，所有关键字有关键字较它小的记录都安置在它的位置之前，所有关键字 较它大的记录都安置在它的位置之后。较它大的记录都安置在它的位置之后。由此可由此可以该枢轴记录所在的位置以该枢轴记录所在的位置i作分界线作分界线，将序列分割成两，将序列分割成两 个子序列个

30、子序列:L.rs,L.rs+1,L.ri-1和和 L.ri+1,L.ri+2,L.rt 这个过程称作一趟快速排序。这个过程称作一趟快速排序。（3）对子序列）对子序列L.rs,L.rs+1,L.ri-1和和L.ri+1,L.ri+2,L.rt 分别重复（分别重复（1）、（）、（2）。）。26在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确一趟快速排序的具体做法：一趟快速排序的具体做法：(1)附设两个指针附设两个指针i和和j，它们的初值分别为，它们的初值分别为s和和t，设枢，设枢 轴记录的关键字为轴记录的关键字为pivotkeyL.rs.

31、key.(2)从从j所指位置起向前搜索找到第一个关键字所指位置起向前搜索找到第一个关键字小于小于 pivotkey的记录和枢轴记录互相交换，然后从的记录和枢轴记录互相交换，然后从i所所 指位置起向后搜索，找到第一个关键字指位置起向后搜索，找到第一个关键字大于大于 pivotkey的记录和枢轴记录互相交换的记录和枢轴记录互相交换;(3)重复重复(2)直到直到i=j为止。为止。例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)27在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深

32、，所提出的问题也很明确第一趟快速排序：第一趟快速排序：初始关键字初始关键字49 38 65 97 76 13 27 49pivotkey=ijj进行进行1次交换之后次交换之后27 38 65 97 76 13 49 49iji进行进行2次交换之后次交换之后27 38 49 97 76 13 65 49ijj进行进行3次交换之后次交换之后27 38 13 97 76 49 65 49iji进行进行4次交换之后次交换之后27 38 13 49 76 97 65 49ijj完成一趟排序完成一趟排序27 38 13 49 76 97 65 4928在整堂课的教学中，刘教师总是让学生带着问题来学习，而问

33、题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Int partition(sqlist&L,int low,int high)pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.rlowL.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rlowL.rhigh;return low;29在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Int partition(sqlist&L,int low,int high)

34、L.r0=L.rlow;pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.rlow=L.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rlow=L.r0;return low;30在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确快速排序算法的实现：快速排序算法的实现：Void Qsort(sqlist&L,int low,int high)if(lowhigh)pivotloc=part

35、ition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);31在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确整个快速排序过程整个快速排序过程:初始关键字初始关键字49 38 65 97 76 13 27 49第一趟快速排序：第一趟快速排序：27 38 13 49 76 97 65 49第二趟快速排序：第二趟快速排序：13 27 3849 65 76 97结束结束结束结束第三趟快速排序：第三趟快速排序：49 65结束结束结束结束有序序列：有序序列：13 27

36、38 49 49 65 76 97第四趟快速排序：第四趟快速排序：32在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确快速排序算法的性能分析：快速排序算法的性能分析：（1）空间：需一个栈空间来实现递归。）空间：需一个栈空间来实现递归。（3）时间：基本运算：比较关键字和移动记录操作）时间：基本运算：比较关键字和移动记录操作 平均时间复杂度：平均时间复杂度：Tavg(n)=快速排序算法的改进：三者取中法快速排序算法的改进：三者取中法 若初始记录序列按关键字有序或基本有序时，快速排若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡

37、排序，时间复杂度为序将蜕化为起泡排序，时间复杂度为O（n*n)。用用“三者取中三者取中”的法则来选取枢轴，即比较的法则来选取枢轴，即比较L.rs.key、L.rt.key和和L.r(s+t)/2.key，取三者中其关键字为中间值，取三者中其关键字为中间值的记录为枢轴。的记录为枢轴。33在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确10.4选择排序选择排序选择排序的基本思想选择排序的基本思想:每一趟在每一趟在n-i+1(i=1,2,.n-1)个记录中个记录中 选取关键字最小的记录作为有序序选取关键字最小的记录作为有序序 列中第列中第i

38、个记录。个记录。选择排序选择排序简单选择排序简单选择排序树形选择排序树形选择排序堆排序堆排序10.4.1简单选择排序简单选择排序简单选择排序的算法设计简单选择排序的算法设计:(1)需进行需进行n-1趟选择操作趟选择操作;(2)第第i趟选择操作为趟选择操作为:通过通过n-i次关键字间比较次关键字间比较,从从n-i+1个记录中选出关个记录中选出关 键字最小的记录键字最小的记录,并和第并和第i个记录交换个记录交换;34在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确简单选择排序的算法实现简单选择排序的算法实现:Void selectsort

39、(sqlist&L)for(i=1;iL.length;+i)j=selectminkey(L,i);if (i!=j)L.riL.rj;算法性能分析算法性能分析:(1)空间空间:一个辅助空间一个辅助空间;(2)时间时间:基本操作基本操作:关键字的比较和记录的移动关键字的比较和记录的移动;关键字的比较次数关键字的比较次数:(n-1)+(n-2)+1=n(n-1)/2 记录的移动次数记录的移动次数:0+3(n-1)/2=3(n-1)/235在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确10.4.2 树形选择排序树形选择排序在简单选择排

40、序中在简单选择排序中,在在n个关键字中进行个关键字中进行n-1次比较选出最次比较选出最小值小值,然后继续在剩余的然后继续在剩余的n-1个关键字中进行个关键字中进行n-2次比较选次比较选出次小值出次小值,在在8个数中选出前个数中选出前3个数个数需进行需进行7+6+5=18次比较次比较改进改进在在n个关键字中进行个关键字中进行n-1次比较选出最小值之后次比较选出最小值之后,利用本次利用本次比较的信息比较的信息,在剩余的在剩余的n-1个关键字中并非一定要进行个关键字中并非一定要进行n-2次比较就可选出次小值次比较就可选出次小值,在在8个数中选出前个数中选出前3个数个数只需进行只需进行11次比较次比较

41、36在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确例例:有有8个运动员参加体育锦标比赛个运动员参加体育锦标比赛,要决出前要决出前3名名,比赛规比赛规则则 依据依据:若甲胜乙若甲胜乙,乙胜丙乙胜丙,则甲胜丙的原则则甲胜丙的原则;则此则此8名运动名运动员员 需进行需进行11场比赛场比赛,而不是而不是18场场.选拔冠军的比赛程序选拔冠军的比赛程序:BAOHELILIUBAOLILINBAOHUWUXEILINLINHUBAO需进行需进行7场比赛场比赛37在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深

42、，所提出的问题也很明确选拔亚军的比赛程序选拔亚军的比赛程序:LIHELILIULIULILIN*HUWUXEILINLINHULIN需进行需进行2场比赛场比赛选拔季军的比赛程序选拔季军的比赛程序:LIHELILIULIULI*HUWUXEIWUHUHUHU需进行需进行2场比赛场比赛38在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 又称锦标赛排序，首先对又称锦标赛排序，首先对n个记录的关键字进行两两比较，然个记录的关键字进行两两比较，然后在其中一半较小者之间再进行两两比较，如此重复，直到选出最后在其中一半较小者之间再进行两两比较，如

43、此重复，直到选出最小关键字的记录为止。小关键字的记录为止。树形选择排序的基本思想树形选择排序的基本思想:树形选择排序算法的执行步骤树形选择排序算法的执行步骤:用一棵有用一棵有n个叶子结点的完全二叉树表示排序过程个叶子结点的完全二叉树表示排序过程:(1)n个叶子结点依次存放排序之前的个叶子结点依次存放排序之前的n个关键字个关键字;(2)构造非叶子结点构造非叶子结点:每个非叶子结点的值为其左、右孩子结点中的每个非叶子结点的值为其左、右孩子结点中的 较小值，则根结点是所有叶子中的最小关键字，输出根结点的值；较小值，则根结点是所有叶子中的最小关键字，输出根结点的值；(3)修改非结点的关键字：把据有根结

44、点值的叶子结点的值改为修改非结点的关键字：把据有根结点值的叶子结点的值改为“最最 大值大值”，然后从叶子开始，和其左（或右）兄弟的值进行比较，然后从叶子开始，和其左（或右）兄弟的值进行比较，修改从叶子结点到根的路径上各结点的值，输出根结点的值；修改从叶子结点到根的路径上各结点的值，输出根结点的值；(4)重复（重复（3），直到输出），直到输出n个值为止。个值为止。39在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确49 38976576 13 27 4949 38976576 13 27 4938651327381313输出输出1349

45、 38976576 27 4938657627382727例例:一组待排序的记录的关键字初始如下一组待排序的记录的关键字初始如下:(49,38,65,97,76,13,27,49)输出输出2749 38976576 4938657649384938输出输出3840在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确算法性能分析算法性能分析:(1)空间空间:较多辅助空间较多辅助空间;(2)时间时间:基本操作基本操作:关键字的比较和记录的移动关键字的比较和记录的移动;算法时间复杂度：算法时间复杂度：10.4.3 堆排序堆排序堆的定义堆的定义:

46、n个元素的序列个元素的序列k1,k2,.,kn当且仅当满足下列关系时，当且仅当满足下列关系时，称之为堆称之为堆:关系一：关系一：ki=k2i)关系二：关系二：ki=k2i+1)（i=1,2,.,|n/2|)41在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确若将和此序列对应的一维数组看成是一个完全二叉树若将和此序列对应的一维数组看成是一个完全二叉树,则则堆的含义表明堆的含义表明:（1）完全二叉树中所有非叶子结点的值均不大）完全二叉树中所有非叶子结点的值均不大(小小)于其于其 左、右孩子结点的值。左、右孩子结点的值。（2）若序列）若序列

47、k1,k2,.,kn为堆，则堆顶元素（完全二为堆，则堆顶元素（完全二叉树叉树 的根）是序列中的最小的根）是序列中的最小(大大)值。值。例例1：96,83,27,38,11,099683273811 9堆顶元素是序列最大值堆顶元素是序列最大值例例1：12,36,24,85,47,30,53堆顶元素是序列最小值堆顶元素是序列最小值1236248547 305342在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确堆排序堆排序若在输出堆顶元素之后，使得剩余若在输出堆顶元素之后，使得剩余n-1个元素个元素的序列重又建成一个堆，则得到的序列重又建

48、成一个堆，则得到n个元素中的个元素中的次小值。如此反复执行，便能得到一个有序序次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。列，这个过程称之为堆排序。堆排序要解决两个问题：堆排序要解决两个问题：1、如何由一个无序序列建成一个堆？、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素之后，、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？调整剩余元素成为一个新的堆？问题问题2的解决的解决:(1)输出堆顶元素输出堆顶元素;(2)用堆中最后一个元素代替堆顶元素用堆中最后一个元素代替堆顶元素;(3)从堆顶至叶子进行调整从堆顶至叶子进行调整(筛选筛选);43在整堂课的教学中，刘教

49、师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确例例:有一个堆如下有一个堆如下:1397273849657649输出输出1397替代堆顶替代堆顶9713273849657649筛选筛选27139738496576492713493897657649输出输出2797替代堆顶替代堆顶44在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确9713493827657649筛选筛选38134997276576493813494927657697输出输出3865替代堆顶替代堆顶结论结论:对于一个具有对于一个具有

50、n个结点的堆个结点的堆,经过经过n次输出、次输出、n-2次筛选，则可次筛选，则可得到一个关键字递增的输出序列和一个关键字递减的数组得到一个关键字递增的输出序列和一个关键字递减的数组r；971365762738494945在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确问题问题1的解决：的解决：（1）将此无序序列看成是一个完全二叉树，则最后一个）将此无序序列看成是一个完全二叉树，则最后一个 非叶子结点是第非叶子结点是第|n/2|个元素。个元素。（2）依次对第）依次对第|n/2|，|n/2|-1,|n/2|-2,1个元素进行筛选。个元素进