数据结构-第8章-排序.pptx

《数据结构-第8章-排序.pptx》由会员分享，可在线阅读，更多相关《数据结构-第8章-排序.pptx（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构 新世纪应用型高等教育新世纪应用型高等教育计算机类课程规划教材计算机类课程规划教材新世纪应用型高等教育教材编审委员会新世纪应用型高等教育教材编审委员会 组编组编 主编主编 曹春萍曹春萍8.1 排序的基本概念第第8 8章章排排 序序排序排序(sorting)，简单来讲，是指把一组任意顺序的数据序列重新排列成有序的序列。如某，简单来讲，是指把一组任意顺序的数据序列重新排列成有序的序列。如某班的学生成绩，如表班的学生成绩，如表8-1所示，其中的声乐成绩本为一组任意排列的数据（所示，其中的声乐成绩本为一组任意排列的数据（62，66，70，58，58，75），经过一定的操作后得到一组有序的序列（

2、），经过一定的操作后得到一组有序的序列（58，58，62，66，70，75或或75，70，66，62，58，58），此即为排序。），此即为排序。所谓排序就是把序列中的记录按关键字非递减所谓排序就是把序列中的记录按关键字非递减(或非递增或非递增)的顺序重新排列起来。假设含有的顺序重新排列起来。假设含有n个记录的序列为个记录的序列为R1，R2，Rn，其相应的关键字序列为，其相应的关键字序列为K1，K2，Kn，对其，对其进行排序是指将这进行排序是指将这n个记录按照个记录按照K1，K2，Kn的大小顺序来重新排列。对表的大小顺序来重新排列。对表8-1中的记录而中的记录而言，按照不同的科目来排序，可得到不

3、同的有序序列。言，按照不同的科目来排序，可得到不同的有序序列。8.1 排序的基本概念第第8 8章章排排 序序内部排序的方法有很多，按策略可以分为五类：插入排序、交换排序、选择排序、归并排内部排序的方法有很多，按策略可以分为五类：插入排序、交换排序、选择排序、归并排序和基数排序。这些排序方法各有优缺点，用于不同的场合，很难概括的来讲一种方法比另一序和基数排序。这些排序方法各有优缺点，用于不同的场合，很难概括的来讲一种方法比另一种方法好，一定要根据待排序序列的初始状态、具体要求来选择合适的排序方法。通常评价排种方法好，一定要根据待排序序列的初始状态、具体要求来选择合适的排序方法。通常评价排序方法好

4、坏的标准主要有两条：时间复杂度和空间复杂度。时间复杂度主要是分析记录关键字序方法好坏的标准主要有两条：时间复杂度和空间复杂度。时间复杂度主要是分析记录关键字的比较次数和记录的移动次数；空间复杂度为算法中使用的内存辅助空间的多少。另外稳定性的比较次数和记录的移动次数；空间复杂度为算法中使用的内存辅助空间的多少。另外稳定性也是评价排序性能的一方面。也是评价排序性能的一方面。大多数排序算法都有两个基本的操作：比较两个关键字的大小；移动记录。其中移动记录大多数排序算法都有两个基本的操作：比较两个关键字的大小；移动记录。其中移动记录的操作依赖于待排序记录的存储方式，不同的存储方式，移动记录操作的实现也不

5、同。的操作依赖于待排序记录的存储方式，不同的存储方式，移动记录操作的实现也不同。8.1 排序的基本概念第第8 8章章排排 序序待排序记录的存储结构和移动记录的实现方式主要有以下几种：待排序记录的存储结构和移动记录的实现方式主要有以下几种：以以顺序表作为存储结构：对记录本身进行物理重排（将记录移到合适的位置）。顺序表作为存储结构：对记录本身进行物理重排（将记录移到合适的位置）。以以链表作为存储结构：无需移动记录，只要修改指针即可。链表作为存储结构：无需移动记录，只要修改指针即可。用用顺序的方式存储待排序的记录，但同时建立一个辅助表顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指

6、向记录位置的如包括关键字和指向记录位置的指针组成的索引表指针组成的索引表)：这时只需对辅助表的表目进行物理重排（即只移动辅助表的表目），而不：这时只需对辅助表的表目进行物理重排（即只移动辅助表的表目），而不移动记录本身。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。移动记录本身。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。8.2 插入排序第第8 8章章排排 序序插入排序的基本思想是：将记录分成两部分，一部分是有序序列，第二部分是待排序插入排序的基本思想是：将记录分成两部分，一部分是有序序列，第二部分是待排序序列；初始时有序序列仅有第一个记录，依次将待排序序列中

7、的记录取出、并插入到有序序列；初始时有序序列仅有第一个记录，依次将待排序序列中的记录取出、并插入到有序序列中的合适位置，使插入后的序列仍保持有序，直至全部待排序记录都插入到有序序列序列中的合适位置，使插入后的序列仍保持有序，直至全部待排序记录都插入到有序序列为止。为止。常用常用的插入排序有直接插入排序和折半插入排序。的插入排序有直接插入排序和折半插入排序。8.2 插入排序第第8 8章章排排 序序8.2.1 8.2.1 直接插入排序直接插入排序1 1基本思想基本思想基本思想基本思想直接插入排序的基本操作是将一个记录插入到一个长度为直接插入排序的基本操作是将一个记录插入到一个长度为m(假设假设)的

8、有序序列中，使之的有序序列中，使之仍保持有序，从而得到一个新的长度为仍保持有序，从而得到一个新的长度为m1的有序序列。的有序序列。假设待排序的记录存放在顺序表假设待排序的记录存放在顺序表L1.n中，其中中，其中L0为哨兵。初始时，为哨兵。初始时，L1自成自成1个有序个有序序列，序列，L2.n为待排序序列。依次将为待排序序列。依次将Li（2in）插入当前的有序序列）插入当前的有序序列L1.i-1中，生成含中，生成含n个记录的有序序列。每个记录的一次插入成为一趟直接插入排序。个记录的有序序列。每个记录的一次插入成为一趟直接插入排序。我们用我们用8.1节中学生记录的例子来说明直接插入排序的过程。其关

9、键字序列（社会实践成节中学生记录的例子来说明直接插入排序的过程。其关键字序列（社会实践成绩）为绩）为11，10，16，13，2，10（用下划线对两个相同的关键字加以区分），按照上述思（用下划线对两个相同的关键字加以区分），按照上述思想，其直接插入排序的过程如图想，其直接插入排序的过程如图8-1所示。其中所示。其中中的序列为已排好序的部分。中的序列为已排好序的部分。8.2 插入排序第第8 8章章排排 序序8.2 插入排序第第8 8章章排排 序序2 2算法实现算法实现算法实现算法实现直接插入排序的实现算法如下：直接插入排序的实现算法如下：voidInsertSort(SortItem L,int

10、n)int i,j;for(i=2;i L0.key;j-)/*移动记录、定位插入位置移动记录、定位插入位置*/Lj+1.key=Lj.key;Lj+1.key=L0.key;/*将将L0即原即原Li记录内容，插到记录内容，插到Lj后一位置后一位置*/其中其中L为待排序的顺序表，为待排序的顺序表，n为顺序表中记录的个数。为顺序表中记录的个数。8.2 插入排序第第8 8章章排排 序序3.3.性能分析性能分析性能分析性能分析算法的主要操作是比较关键字和移动记录（定位插入位置），由两个嵌套的算法的主要操作是比较关键字和移动记录（定位插入位置），由两个嵌套的for循环来实循环来实现。其中第一个现。其中

11、第一个for用于循环顺序表中的每个记录；对不同的顺序表，定位插入位置时需要移用于循环顺序表中的每个记录；对不同的顺序表，定位插入位置时需要移动记录的次数也不同。因此，算法的执行时间同记录的个数以及顺序表中记录的顺序有关。动记录的次数也不同。因此，算法的执行时间同记录的个数以及顺序表中记录的顺序有关。以下分析在极端情况下的时间复杂度并就一般情况作出评价。以下分析在极端情况下的时间复杂度并就一般情况作出评价。（1）最好）最好情况下的时间复杂度情况下的时间复杂度从算法可以看出，当顺序表中的记录本身已经是非递减顺序时：对每趟插入，只做一次从算法可以看出，当顺序表中的记录本身已经是非递减顺序时：对每趟插

12、入，只做一次比较（比较（Lj.key L0.key不成立，退出循环）；定位插入位置时不需要移动记录，只需对不成立，退出循环）；定位插入位置时不需要移动记录，只需对Li做两次移动操作。因此对做两次移动操作。因此对n-1趟插入操作，总的比较次数为趟插入操作，总的比较次数为n-1，移动记录的次数为，移动记录的次数为2(n-1)，所以算法的时间复杂度为，所以算法的时间复杂度为O(n)。8.2 插入排序第第8 8章章排排 序序（2）最坏）最坏情况下的时间复杂度情况下的时间复杂度当顺序表中记录为非递增顺序时：第当顺序表中记录为非递增顺序时：第i趟插入要做趟插入要做i-1次比较，定位第次比较，定位第i（2i

13、n）个记录的）个记录的插入位置需要移动记录的次数为插入位置需要移动记录的次数为i-1+2。所以。所以i-1趟插入的比较次数趟插入的比较次数为为 ，插入次数，插入次数为为 ，所以总的时间复杂度为，所以总的时间复杂度为O(n2)。（3）平均）平均时间复杂度时间复杂度 若顺序表中记录顺序随机，关键字之间的比较次数约为若顺序表中记录顺序随机，关键字之间的比较次数约为n2/4，即时间复杂度为，即时间复杂度为O(n2)。从所需的附加存储空间来看，直接插入排序只需一个监视哨兵，所以其空间复杂度为从所需的附加存储空间来看，直接插入排序只需一个监视哨兵，所以其空间复杂度为O(1)。直接插入排序只涉及到相邻两个记

14、录之间的比较和移动位置，两个关键字相同的记录比直接插入排序只涉及到相邻两个记录之间的比较和移动位置，两个关键字相同的记录比较时不会交换位置，所以直接插入排序是稳定的。较时不会交换位置，所以直接插入排序是稳定的。8.3 交换排序第第8 8章章排排 序序8.3.1 8.3.1 冒泡顺序冒泡顺序1.1.基本思想基本思想基本思想基本思想冒泡排序是一种简单的排序方法，关键字较小的记录经过与其他记录的对比交换，一步冒泡排序是一种简单的排序方法，关键字较小的记录经过与其他记录的对比交换，一步步前移，其排序过程就像气泡从水底逐渐往上冒一样。步前移，其排序过程就像气泡从水底逐渐往上冒一样。假设假设有有n个记录的

15、待排序序列存放在顺序表个记录的待排序序列存放在顺序表L1.n中，首先将第中，首先将第n个记录的关键字和第个记录的关键字和第n-1个记录的关键字相比较，如果为逆序（即个记录的关键字相比较，如果为逆序（即Ln-1.keyLn.key），则将两个记录相互交换，），则将两个记录相互交换，然后比较第然后比较第n-1个记录和第个记录和第n个记录的关键字。依次类推，直到第个记录的关键字。依次类推，直到第2个记录的关键字和第个记录的关键字和第1个记个记录的关键字相比为止，这个过程称作一趟冒泡排序，其结果使得关键字最小的记录移到了最录的关键字相比为止，这个过程称作一趟冒泡排序，其结果使得关键字最小的记录移到了最

16、前面（存入前面（存入L1中）。然后进行第二趟排序，对后中）。然后进行第二趟排序，对后n-1个记录进行排序，其结果使得关键字次个记录进行排序，其结果使得关键字次大的记录交换到了大的记录交换到了L2中（后中（后n-1个记录的最前面）个记录的最前面）。8.3 交换排序第第8 8章章排排 序序第第i趟排序是从第趟排序是从第n个记录开始，两两比较记录的关键字，若为逆序则交换两记录的位置，个记录开始，两两比较记录的关键字，若为逆序则交换两记录的位置，直到比较第直到比较第i+1个记录和第个记录和第i个记录的关键字位置。第个记录的关键字位置。第i趟排序的结果使得关键字第趟排序的结果使得关键字第i小的记录交小的

17、记录交换到了顺序表的第换到了顺序表的第i个位置上（后个位置上（后n-i+1个记录的最前面）。整个排序过程需进行个记录的最前面）。整个排序过程需进行n-1冒泡趟排冒泡趟排序。如果在一趟排序过程中没有交换记录，则说明序列的关键字已经有序，此时可以提前结序。如果在一趟排序过程中没有交换记录，则说明序列的关键字已经有序，此时可以提前结束排序。束排序。8.3 交换排序第第8 8章章排排 序序同样以同样以8.1节中的学生记录为例。对其关键字序列（社会实践成绩）节中的学生记录为例。对其关键字序列（社会实践成绩）11，10，16，13，2，10，图，图8-2给出了每一趟冒泡排序的过程，其中给出了每一趟冒泡排序

18、的过程，其中中的序列为已排好序的部分。第四趟排序中的序列为已排好序的部分。第四趟排序并没有交换记录，说明整个序列都已有序，可以提前结束排序。并没有交换记录，说明整个序列都已有序，可以提前结束排序。8.3 交换排序第第8 8章章排排 序序2.算法实现算法实现冒泡排序的实现算法如下：冒泡排序的实现算法如下：void BubbleSort(SortItem L,int n)int i,j,isChange;for(i=1;i i;j-)/*对第对第i趟的后趟的后n-i+1个记录排序个记录排序*/if(Lj-1.key Lj.key)/*如果逆序，交换记录如果逆序，交换记录*/L0.key=Lj.ke

19、y;Lj.key=Lj-1.key;Lj-1.key=L0.key;isChange=1;/*交换记录的标识置为交换记录的标识置为1*/if(isChange=0)/*第第i趟如果没有交换记录则退出循环趟如果没有交换记录则退出循环*/break;其中其中L为待排序的顺序表，为待排序的顺序表，n为顺序表中记录的个数为顺序表中记录的个数。8.3 交换排序第第8 8章章排排 序序3.3.性能分析性能分析性能分析性能分析从从冒泡排序的算法可以看出若待排序的序列本身就是非递减顺序，则只需进行一趟排序，冒泡排序的算法可以看出若待排序的序列本身就是非递减顺序，则只需进行一趟排序，这一趟排序中共进行这一趟排序

20、中共进行n-1次关键字的比较，并且不需要交换记录。因此，最好情况下的时间复杂次关键字的比较，并且不需要交换记录。因此，最好情况下的时间复杂度为度为O(n)。若若待排序的序列为逆序，则需进行待排序的序列为逆序，则需进行n-1趟排序，共需的比较次数趟排序，共需的比较次数为为 =(n2-n)/2，记录的交换次数记录的交换次数为为 =3(n2-n)/2。则最坏情况下的时间复杂度为。则最坏情况下的时间复杂度为O(n2)。通常通常情况下，可以认为冒泡排序的时间复杂度为情况下，可以认为冒泡排序的时间复杂度为O(n2)。整个序列越接近有序，需要的排序。整个序列越接近有序，需要的排序趟数越少。趟数越少。冒泡排序

21、只在交换记录时需要一个临时记录空间，所以其空间复杂度为冒泡排序只在交换记录时需要一个临时记录空间，所以其空间复杂度为O(1)。另外，冒泡。另外，冒泡排序是稳定的排序方法。排序是稳定的排序方法。8.3 交换排序第第8 8章章排排 序序8.3.2 8.3.2 快速排序快速排序1 1.基本思想基本思想基本思想基本思想快速排序是一种基于分治法的排序方法。首先选取一个记录（通常可选第一个记录）作快速排序是一种基于分治法的排序方法。首先选取一个记录（通常可选第一个记录）作为枢轴，通过一趟排序将待排序记录分割成两子序列，其中枢轴左面记录的关键字都不大于为枢轴，通过一趟排序将待排序记录分割成两子序列，其中枢轴

22、左面记录的关键字都不大于枢轴的关键字，枢轴右面记录的关键字都不小于枢轴的关键字。对枢轴的左右两个子序列递枢轴的关键字，枢轴右面记录的关键字都不小于枢轴的关键字。对枢轴的左右两个子序列递归实施这一过程，将待排序的序列划分成更小的子序列，直至每个子序列只包含一个记录为归实施这一过程，将待排序的序列划分成更小的子序列，直至每个子序列只包含一个记录为止。最终使得整个序列都有序。止。最终使得整个序列都有序。8.3 交换排序第第8 8章章排排 序序2.2.算法实现算法实现算法实现算法实现8.3 交换排序第第8 8章章排排 序序2.2.算法实现算法实现算法实现算法实现8.3 交换排序第第8 8章章排排 序序

23、3.3.性能分析性能分析性能分析性能分析从快速排序的算法可以看出，记录的移动次数通常小于记录的比较次数，因此讨论快速从快速排序的算法可以看出，记录的移动次数通常小于记录的比较次数，因此讨论快速排序算法的时间复杂度只要按记录的比较次数来讨论即可。对长度为排序算法的时间复杂度只要按记录的比较次数来讨论即可。对长度为k的序列进行一趟排序，的序列进行一趟排序，需要的比较次数为需要的比较次数为k-1。最坏最坏情况下，当每次选取的枢轴都为其（子）序列中的最大（或最小）记录时，划分出情况下，当每次选取的枢轴都为其（子）序列中的最大（或最小）记录时，划分出来的两个子序列一个为空，另一个仅比原序列少一个枢轴记录

24、。此时对包含来的两个子序列一个为空，另一个仅比原序列少一个枢轴记录。此时对包含n个记录的序列需个记录的序列需要进行要进行n-1趟快速排序，第趟快速排序，第i趟快速排序的比较次数为趟快速排序的比较次数为n-i，则总的比较次数，则总的比较次数为为 。此时算法的时间复杂度为此时算法的时间复杂度为O(n2)。8.3 交换排序第第8 8章章排排 序序4.4.枢轴的选取枢轴的选取枢轴的选取枢轴的选取对于随机序列，选取第一个记录作为枢轴是一种简单有效的方法。但是若初始记录序列对于随机序列，选取第一个记录作为枢轴是一种简单有效的方法。但是若初始记录序列按关键字有序或基本有序时，用第一个记录作为枢轴，将会使大部

25、分记录都划分到一个子区按关键字有序或基本有序时，用第一个记录作为枢轴，将会使大部分记录都划分到一个子区间中，快速排序将蜕化为冒泡排序。间中，快速排序将蜕化为冒泡排序。另另一种改进的方法是依三者取中的原则来选取枢轴。即比较第一个、中间一个和最后一一种改进的方法是依三者取中的原则来选取枢轴。即比较第一个、中间一个和最后一个记录的关键字，取关键字居中的记录作为枢轴。经验证明，采用三者取中的规则可大大改个记录的关键字，取关键字居中的记录作为枢轴。经验证明，采用三者取中的规则可大大改善快速排序中最坏情况下的性能。善快速排序中最坏情况下的性能。8.4 选择排序第第8 8章章排排 序序8.4.1 8.4.1

26、 简单选择排序简单选择排序1 1.基本思想基本思想基本思想基本思想简单选择排序又称直接选择排序，是一种很简单的排序方法：首先在待排序序列的所有简单选择排序又称直接选择排序，是一种很简单的排序方法：首先在待排序序列的所有记录中选出关键字最小的记录，把它与第一个记录互换；然后在其余的记录中再选出关键字记录中选出关键字最小的记录，把它与第一个记录互换；然后在其余的记录中再选出关键字最小的记录与第二个记录互换；第最小的记录与第二个记录互换；第i趟在后趟在后n-i+1(i=1,2,.,n-1）个记录中选取键值最小的记录）个记录中选取键值最小的记录与序列的第与序列的第i个记录互换；依此类推，直至所有记录排

27、序完成。个记录互换；依此类推，直至所有记录排序完成。8.4 选择排序第第8 8章章排排 序序对学生记录中的关键字序列（社会实践成绩）对学生记录中的关键字序列（社会实践成绩）11，10，16，13，2，10进行简单选择进行简单选择排序，其过程如图排序，其过程如图8-5所示。所示。图图8-5 简单选择排序过程示意图简单选择排序过程示意图8.4 选择排序第第8 8章章排排 序序2.2.算法实现算法实现算法实现算法实现简单选择排序的算法如下：简单选择排序的算法如下：void SelectSort(SortItem L,int n)int i,j,k;for(i=1;i n;i+)/*需进行需进行n-1

28、趟选择和交换趟选择和交换*/k=i;/*用用k记录当前最小记录的下标记录当前最小记录的下标*/for(j=i+1;j=n;j+)if(Lj.key Lk.key)/*查到关键字更小的记录查到关键字更小的记录*/k=j;if(k!=i)/*Li和和Lk互换互换*/L0.key=Li.key;Li.key=Lk.key;Lk.key=L0.key;8.4 选择排序第第8 8章章排排 序序3.3.性能分析性能分析性能分析性能分析对对n个记录序列进行简单选择排序，需进行个记录序列进行简单选择排序，需进行n-1趟排序，第趟排序，第i趟排序需进行趟排序需进行n-i-1次比较，每次比较，每趟排序最多需要移动

29、趟排序最多需要移动3次记录。所以总的比较次数为次记录。所以总的比较次数为 ，记录的最大移动次数为，记录的最大移动次数为3(n-1)。因此算。因此算法的时间复杂度为法的时间复杂度为O(n2)。简单简单选择排序的空间复杂度为选择排序的空间复杂度为O(1)。简单选择排序会交换两个不相邻的记录，所以是不稳定的排序方法。简单选择排序会交换两个不相邻的记录，所以是不稳定的排序方法。8.4 选择排序第第8 8章章排排 序序8.4.2 8.4.2 堆排序堆排序1.1.算法描述算法描述算法描述算法描述堆排序的思想是：把待排序的序列存于顺序表中，此时关键字序列不一定符合堆的条件。堆排序的思想是：把待排序的序列存于

30、顺序表中，此时关键字序列不一定符合堆的条件。首先建成一个初始堆（大根堆），然后输出堆顶记录，让堆中最后一个记录上移到原堆顶位首先建成一个初始堆（大根堆），然后输出堆顶记录，让堆中最后一个记录上移到原堆顶位置，再恢复堆。重复输出堆顶记录、堆尾记录上移、恢复堆的操作，直到堆中只有一个记录置，再恢复堆。重复输出堆顶记录、堆尾记录上移、恢复堆的操作，直到堆中只有一个记录为止。由于每次都是从当前堆中输出关键字最大的记录，所以整个输出过程就完成了对序列为止。由于每次都是从当前堆中输出关键字最大的记录，所以整个输出过程就完成了对序列的排序。的排序。堆堆顶定义如下：顶定义如下：n个记录的序列个记录的序列k1,

31、k2,.ki,ki+1,.kn，当且仅当其关键字满足条件如下条，当且仅当其关键字满足条件如下条件时，才称之为堆。件时，才称之为堆。8.4 选择排序第第8 8章章排排 序序堆堆排序的关键操作为：初始化堆，每趟排序时的输出堆顶记录和恢复堆。堆顶记录是当排序的关键操作为：初始化堆，每趟排序时的输出堆顶记录和恢复堆。堆顶记录是当前堆中关键字最大的记录，并且输出的堆顶记录，被依次从后往前存入顺序表中，所以如果前堆中关键字最大的记录，并且输出的堆顶记录，被依次从后往前存入顺序表中，所以如果要对序列进行非递减排序，则需对原序列建立一个大根堆。要对序列进行非递减排序，则需对原序列建立一个大根堆。（1）初始化堆

32、）初始化堆设待排序的设待排序的n个记录存放在顺序表个记录存放在顺序表L1.n中，中，L中的中的n个记录可以对应一棵完全二叉树，个记录可以对应一棵完全二叉树，但该完全二叉树并不一定满足大根堆的定义，因此要对完全二叉树中的每个结点进行调整。但该完全二叉树并不一定满足大根堆的定义，因此要对完全二叉树中的每个结点进行调整。完全二叉树中的叶子节点都满足大根堆的定义，因此只需从最后一个非叶子结点（编号为完全二叉树中的叶子节点都满足大根堆的定义，因此只需从最后一个非叶子结点（编号为n/2的结点）依次往前调整，直到调整到根结点。的结点）依次往前调整，直到调整到根结点。8.4 选择排序第第8 8章章排排 序序（

33、2）堆排序）堆排序堆排序的过程就是循环输出堆顶记录（关键字最大的记录）、并调整堆的过程，直到堆堆排序的过程就是循环输出堆顶记录（关键字最大的记录）、并调整堆的过程，直到堆中仅有一个记录。具体步骤如下：中仅有一个记录。具体步骤如下：首先利用上述首先利用上述HeapAdjust算法将待排序的序列调整为一个初始堆。算法将待排序的序列调整为一个初始堆。将堆顶记录（将堆顶记录（L1）和堆尾记录（）和堆尾记录（Ln）相互交换，即输出堆顶记录。输出之后，堆）相互交换，即输出堆顶记录。输出之后，堆中记录的个数减一，即中记录的个数减一，即n=n-1，新的堆尾记录的逻辑位置也前移一个位置。，新的堆尾记录的逻辑位置

34、也前移一个位置。交换后，新的堆顶记录可能不符合大根堆的定义；而其它所有结点均满足大根堆顶定交换后，新的堆顶记录可能不符合大根堆的定义；而其它所有结点均满足大根堆顶定义，因此只需对堆顶记录调用义，因此只需对堆顶记录调用HeapAdjust算法重新调整。算法重新调整。重复步骤重复步骤、，直至堆中只有一个记录位置。，直至堆中只有一个记录位置。8.4 选择排序第第8 8章章排排 序序2.2.性能分析性能分析性能分析性能分析8.4 选择排序第第8 8章章排排 序序2.2.性能分析性能分析性能分析性能分析8.4 选择排序第第8 8章章排排 序序2.2.性能分析性能分析性能分析性能分析8.4 选择排序第第8

35、 8章章排排 序序2.2.性能分析性能分析性能分析性能分析8.4 选择排序第第8 8章章排排 序序2.2.性能分析性能分析性能分析性能分析8.5 归并排序第第8 8章章排排 序序1.1.基本思想基本思想基本思想基本思想二二路归并排序的基本思路：路归并排序的基本思路：（1）把）把待排序序列中的待排序序列中的n个记录看成个记录看成n个长度个长度length为为1的有序子序列。的有序子序列。（2）对）对这这n个有序子序列进行两两归并使记录关键字有序，得到个有序子序列进行两两归并使记录关键字有序，得到n/2个长度为个长度为2*length或或为为length（最后一个）的有序子序列。这一过程称为一趟二

36、路归并。（最后一个）的有序子序列。这一过程称为一趟二路归并。（3）重复）重复步骤（步骤（2）直到所有待排序记录归并成一个长度为）直到所有待排序记录归并成一个长度为n的有序序列为止。的有序序列为止。8.5 归并排序第第8 8章章排排 序序对对学生记录中的关键字序列（社会实践成绩）学生记录中的关键字序列（社会实践成绩）11，10，16，13，2，10，二路归并排，二路归并排序的过程如图序的过程如图8-9所示。所示。8.5 归并排序第第8 8章章排排 序序2.2.算法实现算法实现算法实现算法实现（1）两两归并）两两归并假定假定待归并的两个有序子序列分别存于顺序表待归并的两个有序子序列分别存于顺序表L

37、中下标中下标low到下标到下标mid的单元，和下标的单元，和下标mid+1到下标到下标up的单元，结果有序序列存于顺序表的单元，结果有序序列存于顺序表R中从下标中从下标low到下标到下标up的单元的单元。8.5 归并排序第第8 8章章排排 序序2.2.算法实现算法实现算法实现算法实现8.5 归并排序第第8 8章章排排 序序（2）一趟二路归并）一趟二路归并每每一趟二路归并排序都是依次从前往后将相邻的两个子序列进行归并，并且每个子序列的一趟二路归并排序都是依次从前往后将相邻的两个子序列进行归并，并且每个子序列的长度都相等，设为长度都相等，设为len（最后一个子序列长度可能小于（最后一个子序列长度可

38、能小于len），归并的结果存入顺序表），归并的结果存入顺序表R中。则中。则一趟排序的过程为：一趟排序的过程为：从第一个子序列的第一个记录（从第一个子序列的第一个记录（i=1）开始，将子序列）开始，将子序列Li.i+len-1和和Li+len.i+2*len归并；归并；i后移后移2*len个位置，重复步骤（个位置，重复步骤（1）继续归并子序列，直至剩余的记录数不足两个子序）继续归并子序列，直至剩余的记录数不足两个子序列的长度，此时分两种情况来处理：若剩余记录数大于列的长度，此时分两种情况来处理：若剩余记录数大于len，则将其分为记录数为，则将其分为记录数为len的子序列的子序列和由其余记录构成的

39、子序列，并调用和由其余记录构成的子序列，并调用MergeTwo对这两个子序列进行归并；若剩余记录数不大对这两个子序列进行归并；若剩余记录数不大于于len，则将剩余记录依次复制到顺序表，则将剩余记录依次复制到顺序表R中。中。8.5 归并排序第第8 8章章排排 序序（3）二路归并排序）二路归并排序初始初始时每个子序列的长度为时每个子序列的长度为1。每趟二路归并之后子序列的长度扩大一倍（最后一个子序。每趟二路归并之后子序列的长度扩大一倍（最后一个子序列的长度可能例外），子序列的个数减少。经过若干趟二路归并之后，只剩一个子序列，此时列的长度可能例外），子序列的个数减少。经过若干趟二路归并之后，只剩一个

40、子序列，此时完成了二路归并排序。假定待排序的完成了二路归并排序。假定待排序的n个记录存放在顺序表个记录存放在顺序表L中；中；R为存放排序结果的顺序表，为存放排序结果的顺序表，长度也为长度也为n。则整个二路归并排序的算法描述如下：。则整个二路归并排序的算法描述如下：void MergeSort(SortItem L,SeqList R,int n)/*n为顺序表为顺序表L的长度的长度*/int len;for(len=1;len n;len*=2)MergeOnePass(L,R,len,n);8.5 归并排序第第8 8章章排排 序序3.3.性能分析性能分析性能分析性能分析二路归并排序的时间复杂

41、度为归并排序的趟数乘以每趟二路归并排序的时间复杂度。记录二路归并排序的时间复杂度为归并排序的趟数乘以每趟二路归并排序的时间复杂度。记录数为数为n的待排序序列需经的待排序序列需经log2n趟二路归并，每趟二路归并中记录的比较次数和移动次数都约为趟二路归并，每趟二路归并中记录的比较次数和移动次数都约为n（因为每趟归并都是将记录从一个顺序表复制到另一个顺序表）。因此，二路归并排序最好（因为每趟归并都是将记录从一个顺序表复制到另一个顺序表）。因此，二路归并排序最好和最坏时间复杂度均为和最坏时间复杂度均为O(nlog2n)。二二路归并排序需要一个长度同样大小的顺序表来存放排序结果，故二路归并排序的空间复路归并排序需要一个长度同样大小的顺序表来存放排序结果，故二路归并排序的空间复杂度为杂度为O(n)。根据根据算法，如果两个相邻子序列存在关键字相同的记录时，总是前一个子序列中记录先被算法，如果两个相邻子序列存在关键字相同的记录时，总是前一个子序列中记录先被复制，即不会改变相同关键字记录在顺序表中的位置。因此，二路归并排序是稳定的。复制，即不会改变相同关键字记录在顺序表中的位置。因此，二路归并排序是稳定的。感谢收看