(1)--第八章 排序数据结构与算法.ppt

《(1)--第八章 排序数据结构与算法.ppt》由会员分享，可在线阅读，更多相关《(1)--第八章 排序数据结构与算法.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第八章 排序技术n本章的内容与目标本章的内容与目标q排序的基本概念排序的基本概念q插入排序插入排序q交换排序交换排序q选择排序选择排序q归并排序归并排序q分配排序分配排序排序的基本概念排序的基本概念n排序：排序：给定一组给定一组记录记录的集合的集合r1,r2,rn，其关，其关键码分别为键码分别为k1,k2,kn，排序是将这些记录，排序是将这些记录排列成顺序为排列成顺序为rs1,rs2,rsn的一个序列，使得的一个序列，使得相应的关键码满足相应的关键码满足ks1ks2ksn（称为升序）（称为升序）或或ks1ks2ksn（称为降序）（称为降序）n正序：正序：待排序序列中的记录已按关键码排好

2、序。待排序序列中的记录已按关键码排好序。n逆序（反序）：逆序（反序）：待排序序列中记录的排列顺序与待排序序列中记录的排列顺序与排好序的顺序正好相反。排好序的顺序正好相反。排序的基本概念排序的基本概念n排序算法的稳定性：排序算法的稳定性：q假定在待排序的记录集中，存在多个具有相同键值的记录，若经过假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的排序，这些记录的相对次序相对次序仍然保持不变，即在原序列中，仍然保持不变，即在原序列中，ki=kj且且ri在在rj之前，而在排序后的序列中，之前，而在排序后的序列中，ri仍在仍在rj之前，则称这种排序算之前，则称这种排序算法是稳定

3、的；否则称为不稳定的。法是稳定的；否则称为不稳定的。n单键排序：单键排序：根据一个关键码进行的排序；根据一个关键码进行的排序；多键排序：多键排序：根据根据多个关键码进行的排序。多个关键码进行的排序。q设关键码分别为设关键码分别为k1,k2,km，多键排序有两种方法：，多键排序有两种方法：依次对记录进行依次对记录进行m次排序，第一次按次排序，第一次按k1排序，第二次按排序，第二次按k2排序，依排序，依此类推。这种方法要求各趟排序所用的算法是稳定的；此类推。这种方法要求各趟排序所用的算法是稳定的；将关键码将关键码k1,k2,km分别视为字符串依次首尾连接在一起，形成分别视为字符串依次首尾连接在一起

4、，形成一个新的字符串，然后，对记录序列按新形成的字符串排序。一个新的字符串，然后，对记录序列按新形成的字符串排序。多键排序多键排序单键排序单键排序排序的基本概念排序的基本概念q排序的分类排序的分类q记录的存储位置记录的存储位置n内排序：内排序：在排序的整个过程中，待排序的所有记录全部被放在排序的整个过程中，待排序的所有记录全部被放置在内存中置在内存中n外排序外排序：待排序的记录个数太多，需要将一部分记录放置在待排序的记录个数太多，需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。

5、外存之间多次交换数据才能得到排序的结果。q关键码关键码n1.基于比较：基本操作基于比较：基本操作关键码的比较和记录的移动。关键码的比较和记录的移动。n2.不基于比较：根据关键码的分布特征。不基于比较：根据关键码的分布特征。排序的基本概念排序的基本概念n排序算法的性能排序算法的性能1.基本操作基本操作。内排序在排序过程中的基本操作：。内排序在排序过程中的基本操作：n比较比较：关键码之间的比较；：关键码之间的比较；n移动移动：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。2.辅助存储空间辅助存储空间。n辅助存储空间是指在数据规模一定的条件下，除了存放待排序辅助存储空间是指在数据

6、规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。记录占用的存储空间之外，执行算法所需要的其他存储空间。3.算法本身的复杂程度算法本身的复杂程度。插入排序插入排序插入排序n插入排序的主要操作是插入排序的主要操作是插入插入n其基本思想是：每次将一个待排序的记录按其关其基本思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中键码的大小插入到一个已经排好序的有序序列中n直到全部记录排好序为止直到全部记录排好序为止插入排序插入排序n直接插入排序直接插入排序q基本思想基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的

7、i-1个个记录已经排好序。记录已经排好序。q关键问题关键问题n如何构造初始的有序序列？如何构造初始的有序序列？n如何查找待插入记录的插入位置如何查找待插入记录的插入位置?有序序列有序序列无序序列无序序列r r1r r2r ri-1r rir rnr ri+1r r1r r2r ri-1r rir rnr ri+1插入排序插入排序n关键问题关键问题(1)如何构造初始的有序序列？如何构造初始的有序序列？解决方法：解决方法：将第将第1个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第2个记录起依次插入到这个记录起依次插入到这个有序表中，直到将第个有序表中，直到将第n个记录插入。个记录插

8、入。算法描述：算法描述：for(i=2;i=n;i+)插入第插入第i个记录，即第个记录，即第i趟直接插入排序；趟直接插入排序；r 0 1 2 3 4 5 62121181825252222101025*25*插入排序插入排序n关键问题关键问题(2)如何查找待插入记录的插入位置如何查找待插入记录的插入位置?解决方法：解决方法：在在i-1个记录的有序区个记录的有序区r1 ri-1中插入记录中插入记录ri，首先顺序查找，首先顺序查找ri的正确插入位置，然后将的正确插入位置，然后将ri插入到相应位置。插入到相应位置。算法描述：算法描述：r0=ri;j=i-1;while(r0rj)rj+1=rj;j-

9、;r0有两个作用：有两个作用：1.进入循环之前暂存了进入循环之前暂存了ri的值，的值，使得不致于因记录的后移而丢失使得不致于因记录的后移而丢失ri的内容；的内容；2.在查找插入位置的循环中充当在查找插入位置的循环中充当哨兵哨兵。r 0 1 2 3 4 5 621212525i=318182222101025*25*2222插入排序插入排序n直接插入直接插入void insertSort(int r,int n)for(i=2;i=n;i+)r0=ri;j=i-1;while(r0rj)rj+1=rj;j=j-1;rj+1=r0;插入排序插入排序n直接插入直接插入r 0 1 2 3 4 5 62

10、121181825252222101025*25*212121212525i=218182222101025*25*2525i=318182222101025*25*252525252222212110102525222221211010252525*25*252522222121101025*25*2525222221211818101018181818101025*25*i=41818i=6181825*25*i=52222插入排序插入排序n直接插入排序算法性能分析直接插入排序算法性能分析最好情况下（正序）：最好情况下（正序）：每趟比较一次，移动两次每趟比较一次，移动两次 1 12 23

11、34 45 5时间复杂度为时间复杂度为O(n)。比较次数：比较次数：n-1移动次数：移动次数：2(n-1)1 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 45 52 23 34 45 5插入排序插入排序n直接插入排序算法性能分析直接插入排序算法性能分析最坏最坏情况下（逆序或反序）：情况下（逆序或反序）：时间复杂度为时间复杂度为O(n2)。5 54 43 32 21 14 45 53 32 21 13 34 45 52 21 12 23 34 45 51 11 12 23 34 45 54 43 32 21 1比较次数：比较次数：移

12、动次数：移动次数：平均平均情况下（随机排列）：情况下（随机排列）：时间复杂度为时间复杂度为O(n2)。插入排序插入排序n直接插入排序算法性能分析直接插入排序算法性能分析q空间性能：空间性能：需要一个记录的辅助空间。需要一个记录的辅助空间。n直接插入排序算法总结直接插入排序算法总结q直接插入排序算法是一种直接插入排序算法是一种稳定稳定的排序算法。的排序算法。q直接插入排序算法简单、容易实现，适用于待排序记录直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。基本有序或待排序记录较小时。q当待排序的记录个数较多时，大量的比较和移动操作使当待排序的记录个数较多时，大量的比较和

13、移动操作使直接插入排序算法的效率降低。直接插入排序算法的效率降低。插入排序插入排序n希尔排序希尔排序q对直接插入算法进行改进，缩小增量排序对直接插入算法进行改进，缩小增量排序 q改进的着眼点：改进的着眼点：（1）若待排序记录按关键码）若待排序记录按关键码基本有序基本有序时，直接插入排序时，直接插入排序的效率可以大大提高；的效率可以大大提高；（2）由于直接插入排序算法简单，则在待排序记录数量）由于直接插入排序算法简单，则在待排序记录数量n较小较小时效率也很高。时效率也很高。插入排序插入排序n希尔排序希尔排序q基本思想：基本思想：将整个待排序记录将整个待排序记录分割分割成若干个子序列，在成若干个子

14、序列，在子序列内分别进行直接插入排序，待整个序列中的记录子序列内分别进行直接插入排序，待整个序列中的记录基本有序基本有序时，对全体记录进行直接插入排序。时，对全体记录进行直接插入排序。q分组插入：分组插入：n先取一个小于先取一个小于n的整数的整数d1作为第一个增量，把全部记录分组。作为第一个增量，把全部记录分组。n将相隔为将相隔为d1的记录放在同一个组中，先在各组内进行的记录放在同一个组中，先在各组内进行直接插入直接插入排序排序；n然后，取第二个增量然后，取第二个增量d2d1重复上述的分组和排序，直至所取的重复上述的分组和排序，直至所取的增量增量dt=1(dtdt-ld2d1)，即所有记录放在

15、同一组中进行直接，即所有记录放在同一组中进行直接插入排序为止。插入排序为止。插入排序插入排序-希尔排序过程希尔排序过程1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始序列初始序列303008081313d1=4404021212525494925*25*16163030080813132525212125*25*303008084949131316164040d2=2131325252121080825*25*16163030494940402525212125*25*303008081313161640404949d3=108082525212113

16、1325*25*16163030404049490808252513131616212125*25*404030304949插入排序插入排序n希尔排序希尔排序两个关键问题两个关键问题q待排序记录的分割待排序记录的分割n作用：作用：减少待排序记录个数，使整个序列向基本有序发展。减少待排序记录个数，使整个序列向基本有序发展。n将相隔某个将相隔某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。n希尔最早提出的方法是希尔最早提出的方法是d1=n/2，di+1=di/2。q子序列内如何进行直接插入排序子序列内如何进行直接插入排序n在插入记录在插入记录ri时，自时，自ri-d起往前跳跃式（跳跃幅

17、度为起往前跳跃式（跳跃幅度为d）搜索）搜索待插入位置。待插入位置。n在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃d个位置。个位置。n在整个序列中，前在整个序列中，前d个记录分别是个记录分别是d个子序列中的第一个记录，个子序列中的第一个记录，所以从第所以从第d+1个记录开始进行插入。个记录开始进行插入。d1=4404021212525494925*25*1616303008081313插入排序插入排序n希尔排序的性能希尔排序的性能q开始时增量较大，每个子序列中的记录个数较少，从而开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录排序速

18、度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。个数较多，但整个序列已基本有序，排序速度也较快。q希尔排序算法的时间性能是所取希尔排序算法的时间性能是所取增量增量的函数，而到目前的函数，而到目前为止尚未有人求得一种最好的增量序列。研究表明，希为止尚未有人求得一种最好的增量序列。研究表明，希尔排序的时间性能在尔排序的时间性能在O(n2)和和O(nlog2n)之间。之间。q希尔排序是不稳定的希尔排序是不稳定的q希尔排序优于插入排序，但不如快速排序，在问题规模希尔排序优于插入排序，但不如快速排序，在问题规模为中等大小时表现良好为中等大小时表现良好交换排序交换

19、排序交换排序n交换排序的主要操作是交换排序的主要操作是交换交换，其主要思想是：在，其主要思想是：在待排序列中选待排序列中选两个两个记录，将它们的关键码相比较，记录，将它们的关键码相比较，如果如果反序反序（即排列顺序与排序后的次序正好相反）（即排列顺序与排序后的次序正好相反），则，则交换交换它们的存储位置。它们的存储位置。反序则反序则 交换交换rirj交换排序交换排序n起泡排序起泡排序q基本思想：基本思想：两两比较两两比较相邻相邻记录的关键码，如果反序则交记录的关键码，如果反序则交换，直到没有反序的记录为止。换，直到没有反序的记录为止。rj rj+1 ri+1 rn-1 rn 无序区无序区 有序

20、区有序区 1ji-1 已经位于最终位置已经位于最终位置反序则交换反序则交换交换排序交换排序n起泡排序过程示例起泡排序过程示例0505989812126969383853538181050598981212696938385353818105059898121269693838535381810505989812126969383853538181交换排序交换排序n起泡排序中的关键问题起泡排序中的关键问题 在一趟起泡排序中，若有多个记录位于最终位置，应如在一趟起泡排序中，若有多个记录位于最终位置，应如何记载？（如何区分有序区和无序区）何记载？（如何区分有序区和无序区）如何确定起泡排序的范围，使得

21、已经位于最终位置的记如何确定起泡排序的范围，使得已经位于最终位置的记录不参与下一趟排序？录不参与下一趟排序？如何判别起泡排序的结束？如何判别起泡排序的结束？交换排序交换排序n 在一趟起泡排序中，若有多个记录位于最终位置，应如在一趟起泡排序中，若有多个记录位于最终位置，应如何记载？（如何区分有序区和无序区）何记载？（如何区分有序区和无序区）解决方法：解决方法：q用变量用变量exchange记载记录交换的位置，则一趟排序后，记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。

22、换的位置，且从此位置以后的所有记录均已经有序。050598981212696938385353818105059898696981811212exchange3838exchange5353exchange交换排序交换排序n 如何确定起泡排序的范围？如何确定起泡排序的范围？解决方法：解决方法：q设设bound位置的记录是无序区的最后一个记录，则每趟位置的记录是无序区的最后一个记录，则每趟起泡排序的范围是起泡排序的范围是r1 rbound。q在一趟排序后，在一趟排序后，exchange位置之后的记录一定是有序的，位置之后的记录一定是有序的，所以所以bound=exchange。算法描述：算法描述

23、：bound=exchange;/排序范围排序范围for(j=1;jrj+1）/两两比较，若逆序，则交换两两比较，若逆序，则交换 rjrj+1；exchange=j；/记录交换位置记录交换位置 交换排序交换排序n 判别起泡排序的结束？判别起泡排序的结束？解决方法：解决方法：q在每一趟起泡排序之前，在每一趟起泡排序之前，令令exchange的初值为的初值为0，排序过程中，只要有记录排序过程中，只要有记录交换，交换，exchange的值就会的值就会大于大于0q在一趟比较完毕，根据在一趟比较完毕，根据exchange的值是否为的值是否为0来来判别是否有记录交换，从判别是否有记录交换，从而判别整个起泡

24、排序结束而判别整个起泡排序结束算法描述：算法描述：void BubbleSort(int r,int n)exchange=n;while(exchange)bound=exchange;exchange=0；for(j=1;jrj+1)rjrj+1；exchange=j；交换排序交换排序n起泡排序的时间性能起泡排序的时间性能q最好情况（正序）最好情况（正序）时间复杂度为时间复杂度为O(n)。q最坏情况（反序）：最坏情况（反序）：时间复杂度为时间复杂度为O(n2)。q平均情况平均情况 时间复杂度为时间复杂度为O(n2)。1 12 23 34 45 5比较次数：比较次数：n-1移动次数：移动次数

25、：0 5 54 43 32 21 1交换排序交换排序n快速排序快速排序q改进的着眼点：改进的着眼点：在起泡排序中，记录的比较和移动是在在起泡排序中，记录的比较和移动是在相邻相邻单元中进行的，记录每次交换只能上移或下移单元中进行的，记录每次交换只能上移或下移一个一个单元，因而总的比较次数和移动次数较多。单元，因而总的比较次数和移动次数较多。减少总的比较次数和移动次数减少总的比较次数和移动次数增大记录的比较和移动距离增大记录的比较和移动距离较大记录从前面直接移动到后面较大记录从前面直接移动到后面较小记录从后面直接移动到前面较小记录从后面直接移动到前面交换排序交换排序n快速排序的基本思想快速排序的基

26、本思想q首先选一个首先选一个轴值轴值（即比较的基准）（即比较的基准）q通过一趟排序将待排序记录通过一趟排序将待排序记录分割分割成独立的两部分，前一成独立的两部分，前一部分记录的关键码均部分记录的关键码均小于或等于小于或等于轴值，后一部分记录的轴值，后一部分记录的关键码均关键码均大于或等于大于或等于轴值轴值q然后分别对这两部分重复上述方法，直到整个序列有序然后分别对这两部分重复上述方法，直到整个序列有序交换排序交换排序n快速排序的关键问题快速排序的关键问题q如何选择轴值？如何选择轴值？q如何实现分割（称一次划分）？如何实现分割（称一次划分）？q如何处理分割得到的两个待排序子序列？如何处理分割得到

27、的两个待排序子序列？q如何判别快速排序的结束？如何判别快速排序的结束？交换排序交换排序n关键问题关键问题：如何选择轴值？：如何选择轴值？选择轴值的方法：选择轴值的方法：q使用第一个记录的关键码；使用第一个记录的关键码；q选取序列中间记录的关键码；选取序列中间记录的关键码；q比较序列中首位记录、末位记录和中间记录的关键码，比较序列中首位记录、末位记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置取关键码居中的作为轴值并调换到第一个记录的位置q随机选取轴值。随机选取轴值。选择轴值的结果：选择轴值的结果：q决定两个子序列的长度决定两个子序列的长度q子序列的长度最好相等。子序列的长

28、度最好相等。(38,27,55,50,13,49,65)交换排序交换排序n关键问题关键问题：如何实现一次划分？：如何实现一次划分？q设待划分的序列是设待划分的序列是rs rt，设参数，设参数i，j分别指向子序分别指向子序列左、右两端的下标列左、右两端的下标s和和t，令，令rs为轴值为轴值实现方法：实现方法：1、ri为轴值，令为轴值，令j从后从后向前向前扫描，直到扫描，直到rjri，则交换，则交换rj与与ri 的位置，使关键码小（与轴值相比）的记录移动到前面去；的位置，使关键码小（与轴值相比）的记录移动到前面去；1313656527275050383849495555jijj1313383865

29、652727505049495555交换排序交换排序n关键问题关键问题：如何实现一次划分？：如何实现一次划分？2、rj为轴值，令为轴值，令i从前向后扫描，直到从前向后扫描，直到rirj，则交换，则交换rj与与ri 的位置，使关键码大（与轴值比较）的记录移动到后面去；的位置，使关键码大（与轴值比较）的记录移动到后面去；3、重复上述过程，直到、重复上述过程，直到i=j。1313383865652727505049495555jiii1313656527275050494938385555ijjj交换排序交换排序n关键问题关键问题：如何实现一次划分？：如何实现一次划分？131365652727505

30、0383849495555ji13133838656527275050494955551313656527275050494938385555jjiiijijjj交换排序交换排序n一次划分一次划分算法描述算法描述int Partition(int r,int first,int end)i=first;j=end;/初始化初始化 while(ij)while(ij&ri=rj)j-；/右侧扫描右侧扫描 if(ij)rirj;i+;/将较小记录交换到前面将较小记录交换到前面 while(ij&ri=rj)i+；/左侧扫描左侧扫描 if(ij)rjri;j-;/将较大记录交换到后面将较大记录交换到

31、后面 retutn i;/i为轴值记录的最终位置为轴值记录的最终位置交换排序交换排序n关键问题关键问题：如何处理分割得到的两个待排序子序列？：如何处理分割得到的两个待排序子序列？解决方法：解决方法：q对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。13132727383865655050494955551313272750503838494955556565ijij交换排序交换排序n关键问题关键问题：如何处理分割得到的两个待排序子序列？：如何处理分割得到的两个待排序子序列？算法描述：算法描述：void QuickSort(int r,int first,in

32、t end)pivotpos=Partition(r,first,end);/一次划分一次划分 QuickSort(r,first,pivotpos-1);/对前一个子序列进行快速排序对前一个子序列进行快速排序 QuickSort(r,pivotpos+1,end);/对后一个子序列进行快速排序对后一个子序列进行快速排序交换排序交换排序n关键问题关键问题：如何判别快速排序的结束？：如何判别快速排序的结束？解决方法：解决方法：q若待排序列中无记录或只有一个记录，显然已有序，则若待排序列中无记录或只有一个记录，显然已有序，则结束，否则进行递归排序。结束，否则进行递归排序。算法描述：算法描述：voi

33、d QuickSort(int r,int first,int end)/在序列在序列 firstend中递归地进行快速排序中递归地进行快速排序 if(first end)pivotpos=Partition(r,first,end);QuickSort(r,first,pivotpos-1);QuickSort(r,pivotpos+1,end);交换排序交换排序n快速排序的时间性能分析快速排序的时间性能分析最好情况：最好情况：q每一次划分对一个记录定位后，该记录的左侧子表与右每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为侧子表的长度相同，为O(nlog2n)。最坏情况

34、：最坏情况：q每次划分只得到一个比上一次划分少一个记录的子序列每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为（另一个子序列为空），为 O(n2)。平均情况：平均情况：qO(nlog2n)交换排序交换排序n课堂练习：课堂练习：一组记录的关键码为一组记录的关键码为(46,79,56,38,40,84)，用快速排序方，用快速排序方法，以第一个记录为基准的一次划分结果为（法，以第一个记录为基准的一次划分结果为（）A (38,40,46,56,79,84)B (40,38,46,79,56,84)C (40,38,46,56,79,84)D (40,38,46,84,56,79

35、)C选择排序选择排序n选择排序选择排序q选择排序的主要操作是选择排序的主要操作是选择选择，其主要思想是：每趟排序，其主要思想是：每趟排序在当前待排序序列中选出关键码在当前待排序序列中选出关键码最小最小的记录，添加到有的记录，添加到有序序列中。序序列中。有序序列有序序列r r1r r2r ri-1r rir rnr rk无序序列无序序列r rnr ri+1r r1r r2r ri-1r rir ri交换交换最小记录最小记录选择排序选择排序n简单选择排序简单选择排序基本思想：基本思想：q第第i 趟在趟在n-i+1（i=1,2,n-1）个记录中选取关键码最小）个记录中选取关键码最小的记录作为有序序列

36、中的第的记录作为有序序列中的第i个记录。个记录。关键问题关键问题q如何在待排序序列中选出关键码最小的记录？如何在待排序序列中选出关键码最小的记录？q如何确定待排序序列中关键码最小的记录在有序序列如何确定待排序序列中关键码最小的记录在有序序列中的位置？中的位置？选择排序选择排序n简单选择排序示例简单选择排序示例08082121i i=2=2最小者最小者 08交换交换21,08最小者最小者 16交换交换25,16最小者最小者 21交换交换49,2121212828i i=1=125251616494908080808i i=3=32121080828284949212128284949161625

37、25161616162525选择排序选择排序n简单选择排序示例简单选择排序示例i i=4=4最小者最小者 25交换交换25,28i i=5=5最小者最小者 28不交换不交换494921210808282816162525252549492121080816162828252528284949212108081616282825252828无序区只有无序区只有一个记录一个记录选择排序选择排序n简单选择排序简单选择排序q关键问题关键问题1：如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？解决方法：解决方法：q设置一个整型变量设置一个整型变量index，用于记录在一趟比较的过

38、程，用于记录在一趟比较的过程中关键码最小的记录位置。中关键码最小的记录位置。q关键问题关键问题2：如何确定待排序序列中关键码最小的记录如何确定待排序序列中关键码最小的记录在有序序列中的位置？在有序序列中的位置？212128282525161649490808indexindexindex0808index=i;for(j=i+1;j=n;j+)if(rjrindex)index=j;选择排序选择排序n简单选择排序简单选择排序void selectSort(int r,int n)for(i=1;in;i+)index=i;for(j=i+1;j=n;j+)if (rjrindex)index=

39、j;if(index!=i)ririndex;时间复杂度为：时间复杂度为：O(n2)选择排序选择排序n堆排序堆排序q改进的着眼点：改进的着眼点：如何如何减少减少关键码间的关键码间的比较比较次数。若能利次数。若能利用每趟比较后的结果，也就是在找出键值最小记录的同用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。用的比较次数，从而提高整个排序过程的效率。减少关键码间的比较次数减少关键码间的比较次数查找最小值的同时，找出较小值查找最小值的同时，找出较小值选择排序选择

40、排序n堆排序堆排序q堆：堆：具有下列性质的具有下列性质的完全二叉树完全二叉树：每个结点的值都小于或等：每个结点的值都小于或等于其左右孩子结点的值（称为于其左右孩子结点的值（称为小根堆小根堆），或每个结点的），或每个结点的值都大于或等于其左右孩子结点的值（称为值都大于或等于其左右孩子结点的值（称为大根堆大根堆）182032364525385040281.小根堆的根结点是所小根堆的根结点是所有结点的最小者。有结点的最小者。2.较小结点靠近根结点，较小结点靠近根结点，但不绝对。但不绝对。3.大根堆性质类似大根堆性质类似选择排序选择排序n堆排序堆排序q堆与序列：堆与序列：将堆用顺序存储结构来存储，则堆

41、对应一组将堆用顺序存储结构来存储，则堆对应一组序列序列50384540283632201828 50 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用顺序存储采用顺序存储选择排序选择排序n堆排序堆排序基本思想：基本思想：q首先将待排序的记录序列构造成一个堆，此时，选出了首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次大的记录，以此余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录。类推，直到堆中

42、只有一个记录。关键问题关键问题q如何由一个无序序列建成一个堆（即初始建堆）？如何由一个无序序列建成一个堆（即初始建堆）？q如何处理堆顶记录？如何处理堆顶记录？q如何调整剩余记录，成为一个新堆（即重建堆）？如何调整剩余记录，成为一个新堆（即重建堆）？选择排序选择排序n堆调整：堆调整：q在一棵完全二叉树中，根结点的左右子树均是堆，如何在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？调整根结点，使整个完全二叉树成为一个堆？283632163029321630293628321629363028初始状态时，设初始状态时，设28的下标为的下标为k，36的下标是多少

43、？的下标是多少？2*k选择排序选择排序n堆调整堆调整算法描述算法描述void sift(int r,int k,int m)/要筛选结点的编号为要筛选结点的编号为k，堆中最后一个结点的编号为，堆中最后一个结点的编号为m i=k;j=2*i;temp=ri;/将筛选记录暂存将筛选记录暂存 while(j=m)/筛选还没有进行到叶子筛选还没有进行到叶子 if(jm&rjrj)break;else rirj;i=j;j=2*i;选择排序选择排序n如何由无序序列建成堆如何由无序序列建成堆算法描述：算法描述：for(i=n/2;i=1;i-)sift(r,i,n);最后一个结点（叶子）的最后一个结点（叶

44、子）的序号是序号是n，则，则n/2对应的结对应的结点是什么？点是什么？所以，建堆的顺序是从最后一个分支结点开始逐所以，建堆的顺序是从最后一个分支结点开始逐一进行堆调整一进行堆调整50384540283632201828iii选择排序选择排序n如何由无序序列建成堆如何由无序序列建成堆282516321836163216282518362532162818362528323628161825iii选择排序选择排序n关键问题关键问题：如何处理堆顶记录？：如何处理堆顶记录？323628161825 36 28 32 25 18 161 2 3 4 5 6对对应应交换交换 16 28 32 25 18

45、361 2 3 4 5 6对对应应321628361825选择排序选择排序n问题问题：如何调整剩余记录，成为一个新堆？：如何调整剩余记录，成为一个新堆？32162836182516281632361825重建堆只需调整堆顶记录重建堆只需调整堆顶记录选择排序选择排序n堆排序算法堆排序算法void HeapSort(int r,int n)for(i=n/2;i=1;i-)sift(r,i,n);for(i=1;in;i+)r1rn-i+1;sift(r,1,n-i);/初始建堆初始建堆/处理堆顶记录处理堆顶记录/重建堆重建堆选择排序选择排序n堆排序性能分析堆排序性能分析q第第1个个for循环是初

46、始建堆，需要循环是初始建堆，需要O(n)时间；时间；q第第2个个for循环是输出堆顶重建堆，共需要取循环是输出堆顶重建堆，共需要取n-1次堆顶记次堆顶记录，第录，第 i 次取堆顶记录重建堆需要次取堆顶记录重建堆需要O(log2i)时间，需要时间，需要O(nlog2n)时间；时间；q因此整个时间复杂度为因此整个时间复杂度为O(nlog2n)，这是堆排序的，这是堆排序的最好最好、最坏最坏和和平均平均的时间代价。的时间代价。选择排序选择排序n练习：对关键码序列练习：对关键码序列23,17,72,60,25,8,68,71,52进进行堆排序行堆排序1、输出两个最大关键码后的剩余堆是（）、输出两个最大关

47、键码后的剩余堆是（）2、输出两个最小关键码后的剩余堆是（）、输出两个最小关键码后的剩余堆是（）归并排序归并排序归并排序n归并排序归并排序q归并排序的主要操作是归并排序的主要操作是归并归并，其，其主要思想是主要思想是：将若干有：将若干有序序列逐步归并，最终得到一个有序序列序序列逐步归并，最终得到一个有序序列q归并：归并：将两个或两个以上的有序序列合并成一个有序序将两个或两个以上的有序序列合并成一个有序序列的过程。列的过程。归并排序归并排序n二路归并排序二路归并排序q基本思想：基本思想：将一个具有将一个具有n个待排序记录的序列看成是个待排序记录的序列看成是n个个长度为长度为1的有序序列，然后进行两

48、两归并，得到的有序序列，然后进行两两归并，得到n/2个长个长度为度为2的有序序列，再进行两两归并，得到的有序序列，再进行两两归并，得到n/4个长度为个长度为4的有序序列，的有序序列，直至得到一个长度为，直至得到一个长度为n的有序序列的有序序列为止。为止。q关键问题关键问题n如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？n怎样完成一趟归并？怎样完成一趟归并？n如何控制二路归并的结束？如何控制二路归并的结束？归并排序归并排序n关键问题关键问题：如何将两个有序序列合成一个有序序列？：如何将两个有序序列合成一个有序序列？602031544556520 605 3144 556

49、5 60 20 31 5 44 55 65ij5kj20i31j60在归并过程中，可能会破坏原在归并过程中，可能会破坏原来的有序序列，所以，将归并来的有序序列，所以，将归并的结果存入另外一个数组中。的结果存入另外一个数组中。归并排序归并排序n关键问题关键问题：如何将两个有序序列合成一个有序序列？：如何将两个有序序列合成一个有序序列？设相邻的有序序列为设相邻的有序序列为rs rm和和rm+1 rt，归并成一，归并成一个有序序列个有序序列r1s r1t s m m+1 t r s t r1 ijk归并排序归并排序n关键问题关键问题：如何将两个有序序列合成一个有序序列？：如何将两个有序序列合成一个有

50、序序列？算法描述：算法描述：void Merge(int r,int r1,int s,int m,int t)i=s;j=m+1;k=s;while(i=m&j=t)if(ri=rj)r1k+=ri+;else r1k+=rj+;if(i=m)while(i=m)/收尾处理收尾处理 r1k+=ri+;/前一个子序列前一个子序列 else while(j=t)r1k+=rj+;/后一个子序列后一个子序列 归并排序归并排序n关键问题关键问题：怎样完成一趟归并？：怎样完成一趟归并？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31