数据结构及算法-排序.ppt

《数据结构及算法-排序.ppt》由会员分享，可在线阅读，更多相关《数据结构及算法-排序.ppt（116页珍藏版）》请在三一办公上搜索。

1、第八章 排序技术,本章的基本内容是：排序的基本概念插入排序交换排序选择排序归并排序,8.1概 述,排序：将一组“无序”的记录序列,调整为按关键字“有序”的记录序列.,1.排序的基本概念,排序：给定一组记录的集合r1,r2,rn，其相应的关键码分别为k1,k2,kn，排序是将这些记录排列成顺序为rs1,rs2,rsn的一个序列，使得相应的关键码满足非递减关系ks1ks2ksn（称为升序）或非递增关系ks1ks2ksn（称为降序）。,1.排序的基本概念,8.1概 述,假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj

2、之前，而在排序后的序列中，ri一定在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。,排序算法的稳定性：,8.1概 述,1.排序的基本概念,待排序序列中的记录已按关键码排好序。待排序序列中记录的排列顺序与排好序的顺序正好相反。,8.1概 述,1.排序的基本概念,正序：,逆序（反序）：,排序的分类 在排序的整个过程中，待排序的所有记录全部被放置在内存中,不需要访问外存 由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。,8.1概 述,1.排序的基本概念,1.内排序：,2.外排序：

3、,2.内排序算法,1.插入排序 2.交换排序 3.选择排序 4.归并排序,8.1概 述,排序基本过程:是一个逐步扩大记录的有序序列长度的过程,3.排序的基本过程,有序序列区,无序序列区,有序序列区,无序序列区,一趟排序,一趟排序:将无序序列区里一个或几个记录合并到有序序列的过程为一趟排序，有序序列长度增加1个或几个,8.1概 述,4.排序算法的存储结构,从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。,假定2：将待排序的记录序列排序为升序序列。,rn+1,假定1：待排序记录采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。,8.1概 述,内排序

4、算法,1.插入排序 2.交换排序 3.选择排序 4.归并排序,8.1概 述,8.2插入排序,插入排序的主要操作是插入，其基本思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。,举例:有序序列 2,待排序记录 3,6,1,1）直接插入排序2）希尔排序,基本思想：在插入第 i（i1）个记录时，前面的 i-1个记录已经排好序。,直接插入排序,8.2插入排序,直接插入排序过程示例,r 0 1 2 3 4 5 6,21,18,25,22,10,25*,21,21,18,10,第五趟,算法稳定吗？,21,算法思想？,i从第2个数到第n个数 将第i个数插

5、入到有序序列中的合理位置,8.2插入排序,共多少趟？,对于ri，如何查找它的插入位置?如何实现插入？,直接插入排序,需解决的关键问题?,20,25,21,18,26,1)将ri暂存在r02)j=i-1；/从第i-1记录开始查找3)当rjr0时，循环做 rj后移一个位置,j-4)rj+1=r0/将r0插入到位置j+1,22,0 1 2 3 4 5,21,i,j,25,j,22,j,21,8.2插入排序,直接插入排序,20,25,10,18,25,22,0 1 2 3 4 5,10,i,j,25,22,20,10,j,r0的作用?,暂存单元,监视哨,对于ri，如何查找它的插入位置?如何实现插入？,

6、需解决的关键问题?,1)将ri暂存在r02)j=i-1；/从第i-1记录开始查找3)当rjr0时，循环做 rj后移一个位置,j-4)rj+1=r0/将r0插入到位置j+1,j,j,8.2插入排序,void insertSort(int r,int n)for(i=2;i=n;i+)r0=ri;for(j=i-1;r0rj;j-)rj+1=rj;rj+1=r0;,直接插入排序算法,1.i从第2个到第n个记录,做以下循环：1.1将ri暂存在r0 1.2 j=i-1；1.3当rjr0时，循环做：rj后移一个位置,j-1.4 rj+1=r0,8.2插入排序,直接插入排序过程示例,r 0 1 2 3 4

7、 5 6,21,18,25,22,10,25*,21,22,10,25,21,18,25,21,8.2插入排序,直接插入排序练习,12 5 9 20 6 31 24,8.2插入排序,直接插入排序练习,12 5 9 20 6 31 24,初始序列,5 12 9 20 6 31 24,第一趟,5 9 12 20 6 31 24,第二趟,5 9 12 20 6 31 24,第三趟,5 6 9 12 20 31 24,第四趟,第五趟,5 6 9 12 20 31 24,第六趟,5 6 9 12 20 24 31,8.2插入排序,1.基本操作。内排序在排序过程中的基本操作：比较：关键码之间的比较；移动：

8、记录从一个位置移动到另一个位置。2.辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。3.算法本身的复杂程度。,排序算法的性能,8.2插入排序,直接插入排序算法性能分析,最好情况下：,时间复杂度为O(n)。,（正序）,8.2插入排序,直接插入排序算法性能分析,最好情况下（正序）：,最坏情况下（逆序）：,时间复杂度为O(n2)。,时间复杂度为O(n)。,8.2插入排序,平均情况下（随机排列）：,直接插入排序算法性能分析,时间复杂度为O(n2)。,8.2插入排序,空间性能：需要一个记录的辅助空间。直接插入排序算法是一种稳定的排

9、序算法。,直接插入排序算法性能分析,直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。,8.2插入排序,希尔排序,改进的着眼点：（1）由于直接插入排序算法简单，在待排序记录数量n较小时效率也很高。（2）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高；,3,2,1,8.2插入排序,（1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？（2）子序列内如何进行直接插入排序？,需解决的关键问题?,基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待

10、整个序列中的记录基本有序时，对全体记录进行直接插入排序。,希尔排序,20 18 19,6 5 7,1 3 2,20 18 19 6 5 7 1 3 2,8.2插入排序,希尔排序,子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。逐渐缩短“增量”，当缩短为1时就是对全体记录进行排序。,d=3,基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。,8.2插入排序,希尔插入排序过程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,13

11、,d=4,每隔d-1个增量记录分为一组每组内采用直接插入排序,8.2插入排序,算法稳定吗？,解决方法：将相隔某个“增量”的记录组成一个子序列。增量应如何取？希尔最早提出的方法是d1=n/2，di+1=di/2。,关键问题(1)应如何分割待排序记录？,算法描述：for(d=n/2;d=1;d=d/2)以d为增量，进行组内直接插入排序；,8.2插入排序,希尔插入排序过程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,d=4,每隔d分为一组,在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。,for(

12、i=d+1;i=n;i+),8.2插入排序,希尔插入排序过程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,d=4,每隔d分为一组,将插入数据ri暂存入r0j=i-1当rjr0，循环做：rj后移一位j-r0插入到位置j+1,将插入数据ri暂存入r0j=i-d当rjr0且j0，循环做：ri后移d位 j=j-d;r0插入到位置j+d,直接插入排序：,希尔排序：,8.2插入排序,解决方法：在插入记录ri时，自ri-d起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r0只是暂存单元，不是哨兵。当搜索位置0，表示插入位置已找到。在搜索过程中，记

13、录后移也是跳跃d个位置。在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。,关键问题(2)子序列内如何进行直接插入排序？,8.2插入排序,算法描述：,for(i=d+1;i0,关键问题(2)子序列内如何进行直接插入排序？,8.2插入排序,void ShellSort(int r,int n)for(d=n/2;d=1;d=d/2)/以d为增量,组内直接插入排序 for(i=d+1;i0,希尔插入排序,8.2插入排序,希尔排序练习,12 5 9 20 6 31 24,初始序列,第一趟结果d=3,第二趟结果d=2,第三趟结果d=1,12 5 9 20 6 3

14、1 24,6 5 9 20 12 31 24,5 6 9 12 20 24 31,初始化：d=3，d=2 d=1,8.2插入排序,希尔排序算法的时间性能,希尔排序算法的时间性能是所取增量的函数，而到目前为止尚未有人求得一种最好的增量序列。研究表明，希尔排序的时间性能在O(n2)和O(nlog2n)之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n1.3)。希尔排序不稳定,希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。,8.2插入排序,第八章 排序技术,本章的基本内

15、容是：排序的基本概念插入排序交换排序选择排序归并排序,交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。,8.3交换排序,反序则 交换,1）冒泡排序2）快速排序,起泡排序,基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。,8.3交换排序,05,98,12,69,38,53,81,起泡排序过程示例,总共n-1趟,一共做多少趟？,for(i=1;irj+1)rjrj+1;,第i趟的比较范围：,从1到（n-i）,8.3交换排序,1 2 3 4 5 6 7,05,98,1

16、2,69,38,53,81,起泡排序过程示例,提问：一定需要做n-1趟？,如果在一趟排序过程中没有进行过交换操作,则排序结束。,8.3交换排序,解决方法：在每一趟起泡排序之前，令exchange的初值为0。在排序过程中，只要有记录交换，用exchange记录交换发生的位置。这样，在一趟排序结束后，只有当exchange的值不为0才需要继续做下一趟冒泡排序。,关键问题1)：如何判别起泡排序的结束？,int exchange=n;while(exchange)exchange=0;for(j=1;jrj+1)rjrj+1;exchange=j;,for(i=1;irj+1)rjrj+1;,8.3交

17、换排序,05,98,12,69,38,53,81,起泡排序过程示例,提问：每趟排序只能使待排序范围减1吗？,8.3交换排序,05,98,12,69,78,81,30,起泡排序过程示例,如果最后一次交换是(位置j)(位置j+1)，位置j以后的所有记录均已经有序，即下一趟的待排序范围缩短为1到j,j,j+1,8.3交换排序,j,关键问题 2）：如何确定每趟起泡排序的范围？,解决方法：变量exchange记载的是这趟排序中最后一次交换的位置，而下一趟的排序范围是1到exchange。,int exchange=n;while(exchange)bound=exchange;exchange=0;fo

18、r(j=1;jrj+1)rjrj+1;exchange=j;,int exchange=n;while(exchange)exchange=0;for(j=1;jrj+1)rjrj+1;exchange=j;,8.3交换排序,void BubbleSort(int r,int n)exchange=n;/初始的排序范围是所有记录 while(exchange)bound=exchange;exchange=0；for(j=1;jrj+1)rjrj+1；exchange=j；,起泡排序算法,8.3交换排序,起泡排序练习,12 5 9 20 6 31 24,初始序列,第一趟结果,第二趟结果,第三趟

19、结果,第四趟结果,5 9 12 6 20 24 31,5 9 6 12 20 24 31,5 6 9 12 20 24 31,5 6 9 12 20 24 31,8.3交换排序,起泡排序的时间性能分析,最好情况：,时间复杂度为O(n)。,8.3交换排序,（正序）,最坏情况（反序）：,起泡排序的时间性能分析,最好情况（正序）：,时间复杂度为O(n)；,时间复杂度为O(n2)。,平均情况：时间复杂度为O(n2)。,稳定算法,8.3交换排序,内排序算法,1.插入排序 2.交换排序 3.选择排序 4.归并排序,8.1概 述,快速排序,首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的

20、两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。,举例:38 27 55 50 33 30 49 65 30 27 33 38 50 55 49 6527 30 33 38 49 50 55 6527 30 33 38 49 50 55 65,8.3交换排序,算法思想：,快速排序的基本思想,如何选择轴值？如何实现分割（称一次划分）？如何处理分割得到的两个待排序子序列？如何判别快速排序的结束？,需解决的关键问题?,举例:38 27 55 50 33 30 49 65 30 27 33 38 50 55 49 6

21、5,8.3交换排序,选择轴值的方法：1.使用第一个记录的关键码；2.选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；4.随机选取轴值。,关键问题：如何选择轴值？,选取不同轴值的后果：决定两个子序列的长度，期望子序列的长度最好相等。,8.3交换排序,举例:38 27 55 50 33 30 49 65 30 27 33 38 50 55 49 65,27,50,38,49,55,关键问题：如何实现一次划分？,每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面。关键在于数和轴值交换，从前、后两端开始，逐渐向

22、中间轴值逼近的过程。,8.3交换排序,33,27,50,38,49,55,33,关键问题：如何实现一次划分？,8.3交换排序,1）当轴值在前面时，从后往前扫描，后面数逐个和轴值比较，第一个比轴值小的数和轴值换，小的数放在轴值的前面，轴值就位于待排序区域的后面2）当轴值在后面时，从前往后扫描，前面数逐个和轴值比较，第一个比轴值大的数和轴值换，大的数放在轴值的后面，轴值就位于待排序区域的前面3）当扫描到轴值，轴值就完成了一次划分,27,50,38,49,55,33,27,50,38,49,55,33,每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面。关键在于数和轴值交换，从前后两端开始，

23、逐渐向中间轴值逼近的过程。,27,50,38,49,55,33,完成一次划分O(n),30,65,27,50,38,49,55,关键问题：如何实现一次划分？,i=0,j=n-11)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换,8.3交换排序,33,关键问题：如何实现一次划分？,i=0,j=n-11)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换直到i=j结束，完成一次划分，即轴值的位置,8.3交换排序,38,33,38,50,30,27,33,65,49,55,解决方法：设待划分的序列

24、是rs rt，设参数i，j分别指向子序列左、右两端的下标s和t，令rs为轴值，（1）j从后向前扫描，直到rjri，将rj移动到ri的位置(rj与ri交换)，使关键码小（同轴值相比）的记录移动到前面去；（2）i从前向后扫描，直到rirj，将ri移动到rj的位置(ri与rj交换)，使关键码大（同轴值比较）的记录移动到后面去；（3）重复上述过程，直到i=j。,关键问题：如何实现一次划分？,8.3交换排序,关键问题：如何实现一次划分？,算法描述：,int Partition(int r,int first,int end)i=first;j=end;/初始化 while(ij)while(ij/i为轴

25、值的最终位置,1)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换直到i=j结束，完成一次划分，即轴值的位置,38 27 55 13 49,13 27 55 38 49,8.3交换排序,解决方法：对分割得到的两个子序列递归地执行快速排序。,关键问题：如何处理分割得到的两个待排序子序列？,8.3交换排序,33,33,解决方法：若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。,关键问题：如何判别快速排序的结束？,8.3交换排序,33,33,快速排序的过程,第一趟,第二趟,第三趟,8

26、.3交换排序,30,65,27,50,38,49,55,33,33,33,void 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);,算法描述：,关键问题：如何判别快速排序的结束？,38 27 55 13 49,13 27 38 55 49,pivotpos,8.3交换排序,快速排序练习,12 5 9 20 6 31 24,

27、初始序列,第一趟结果,第二趟结果,第三趟结果,6 5 9 12 20 31 24,5 6 9 12 20 31 24,5 6 9 12 20 24 31,8.3交换排序,i=0,j=n-11)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换直到i=j结束，完成一次划分，即轴值的位置,8.3交换排序,思考:1 2 3 4 5第一趟：2 3 4 5第二趟：2 3 4 5第三趟：2 3 4 5第四趟：2 3 4 5,快速排序的时间性能分析,例：38,6,27,55,50,13,49的快速排序递归树如下：,快速排序的递归执行过程可以用递归树描述。,快

28、速排序的时间性能分析,8.3交换排序,第一趟结果,13 6 27 38 50 55 49,第二趟结果,6 13 27 38 49 50 55,最好情况：每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。,快速排序的时间性能分析,T(n)2T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n),8.3交换排序,最坏情况：每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为 O(n2)。,最好情况：每一次划分对一个记录定位后，该记录的左侧子表

29、与右侧子表的长度相同，为O(nlog2n)。,快速排序的时间性能分析,平均情况：为O(nlog2n)。,不稳定算法,1,2,3,4,5,8.3交换排序,5,7,3,2,2*,内排序算法,1.插入排序 2.交换排序 3.选择排序 4.归并排序,8.1概 述,选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。,8.4选择排序,简单选择排序,基本思想：第i 趟在n-i+1（i=1,2,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。,举例：21 25 49 28 16 08,08 25 49 28 16 21,8.4选择排序,简

30、单选择排序示例,i=2,21,28,i=1,25,16,49,08,08,i=3,21,16,i=4,8.4选择排序,i=4,i=5,简单选择排序示例,25,28,for(i=1;in;i+)/从第i个数到第n个数中，选出最小的数和第i个数换,总共执行多少趟？,每趟做什么？,8.4选择排序,设置一个整型变量index，Index初始为i。rindex逐一和后面的数比较，记录在一趟比较过程中关键码最小的记录的下标。,关键问题：如何在无序区（第i个数-第n个数）中选出关键码最小的记录？,21,28,25,16,49,08,index,index,index=i;for(j=i+1;j=n;j+)i

31、f(rjrindex)index=j;,j,8.4选择排序,解决方法：第i趟简单选择排序的待排序区间是ri rn，则ri是无序区第一个记录，所以，将index所记载的关键码最小的记录与ri交换。,关键问题：选出无序区（第i个数-第n个数）中关键码最小的记录后，和第i个数交换,算法描述：if(index!=i)ririndex;,8.4选择排序,void selectSort(int r,int n)for(i=1;irindex;,简单选择排序算法,8.4选择排序,简单选择排序练习,12 5 9 20 6 31 24,初始序列,第一趟结果,第二趟结果,第三趟结果,5 12 9 20 6 31

32、24,5 6 9 20 12 31 24,5 6 9 20 12 31 24,第四趟结果,5 6 9 12 20 31 24,第五趟结果,5 6 9 12 20 31 24,第六趟结果,5 6 9 12 20 24 31,8.4选择排序,简单选择排序算法的性能分析,移动次数：最好情况（正序）：0次,1,2,3,4,8.4选择排序,最坏情况：3(n-1)次,简单选择排序算法的性能分析,移动次数：最好情况（正序）：0次,空间性能：需一个辅助空间。稳定性：是一种不稳定的排序算法。,1,2,3,4,比较次数：,简单选择排序的时间复杂度为O(n2)。,例如：3 3*5 1,8.4选择排序,内排序算法,1

33、.插入排序 2.交换排序 3.选择排序 4.归并排序,8.1概 述,堆的定义,堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大根堆。,大根堆的根结点是所有结点的最大者。,8.4选择排序,堆排序,堆的存储,对结点i，2i为其左孩子，2i+1为右孩子，i/2为双亲,8.4选择排序,1,2,3,4,5,6,7,8,9,10,堆调整,提问：在一棵完全二叉树中，假设根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树为一个堆？,如果结点小于左右孩子，则与左右孩子中大的交换。注意要自堆顶到叶子的进行调整,这个过程称为一次筛选。,8.4选择排序,堆调整,提问：在一棵完全二

34、叉树中，假设根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树为一个堆？,8.4选择排序,void sift(int r,int k,int m)/要筛选结点的编号为k，堆中最后一个结点的编号为m i=k;j=2*i;while(jrj)break;else rirj;i=j;j=2*i;,堆调整算法描述：,ik,j,8.4选择排序,关键问题：如何由一个无序序列建成一个堆？,初始待排序序列:28 25 16 36 18 32,8.4选择排序,关键问题：如何由一个无序序列建成一个堆？,从最后一个非叶子结点开始到根结点结束：将以此结点为根的子树调整为堆，调整的过程就是一次筛选的过程。,初始序

35、列:28 25 16 36 18 32,8.4选择排序,提问：为什么采用这个方法？,算法描述：for(i=n/2;i=1;i-)sift(r,i,n);,选择排序,关键问题：如何由一个无序序列建成一个堆？,最后一个结点（叶子）的序号是n，则最后一个分支结点即为结点n的双亲，其序号是n/2。,首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录。,堆排序,待排序序列:28 36 16 25 18 32,8.4选择排序,基本思想：,算法步骤：1）根据待排序序列初始构造一个堆2）堆上

36、结点数大于1时循环做：堆顶结点和树上最后一个结点换，最后一个结点断链，再调整为一个堆。,堆排序,待排序序列:28 36 16 25 18 32,8.4选择排序,基本思想：,循环做:堆顶结点和树上最后一个结点换，最后一个结点断链，再调整为一个堆,36,32,28,堆排序,8.4选择排序,基本思想：,循环做:堆顶结点和树上最后一个结点换，最后一个结点断链，再调整为一个堆,待排序序列:28 36 16 25 18 32,堆排序,需解决的关键问题?,如何由一个无序序列建成一个堆（即初始建堆）？如何处理堆顶记录？如何调整剩余记录，成为一个新堆（即重建堆）？,8.4选择排序,关键问题：如何处理堆顶记录？,

37、将堆顶和堆的最后一个元素换,8.4选择排序,关键问题：如何处理堆顶记录？,将堆顶和堆的最后一个元素换,8.4选择排序,关键问题：如何调整剩余记录，成为一个新堆？,8.4选择排序,一次筛选过程,堆排序算法,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);/重建堆,8.4选择排序,堆排序过程,12 5 9 20 6 31 24,初建堆:根据待排序序列构建一个堆，输出堆的层序序列,初始堆:31 20 24 5 6 9 12,8.4选择排序,堆排

38、序练习,12 5 9 20 6 31 24,每一趟：堆顶结点和树上最后一个结点换，最后一个结点断链，再调整为一个堆，输出堆的层序遍历,第一趟排序:24 20 12 5 6 9 31,8.4选择排序,堆排序练习,12 5 9 20 6 31 24,第二趟,31,6,5,第二趟排序:20 9 12 5 6 24 31,8.4选择排序,每一趟：堆顶结点和树上最后一个结点换，最后一个结点断链，再调整为一个堆，输出堆的层序遍历,堆排序练习,12 5 9 20 6 31 24,第三趟,第三趟排序:12 9 6 5 20 24 31,8.4选择排序,堆排序练习,12 5 9 20 6 31 24,第四趟,第

39、四趟排序:9 5 6 12 20 24 31,8.4选择排序,堆排序练习,12 5 9 20 6 31 24,第五趟,第六趟结果,第五趟排序:6 5 9 12 20 24 31,第六趟排序:5 6 9 12 20 24 31,8.4选择排序,堆排序练习,12 5 9 20 6 31 24,初始序列,初始堆:31 20 24 5 6 9 12,第一趟排序:24 20 12 5 6 9 31,第二趟排序:20 9 12 5 6 24 31,第三趟排序:12 9 6 5 20 24 31,第四趟排序:9 5 6 12 20 24 31,第五趟排序:6 5 9 12 20 24 31,第六趟排序:5

40、6 9 12 20 24 31,8.4选择排序,堆排序算法的性能分析,第1个for循环是初始建堆，需要O(n)时间；第2个for循环是输出堆顶重建堆，共需要取n-1次堆顶记录，第 i 次取堆顶记录重建堆需要O(log2i)时间，需要O(nlog2n)时间；因此整个时间复杂度为O(nlog2n)，这是堆排序的最好、最坏和平均的时间代价。算法不稳定,8.4选择排序,内排序算法,1.插入排序 2.交换排序 3.选择排序 4.归并排序,8.1概 述,归并排序,归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。,8.5归并排序,归并：将两个或两个以上的有序序列合并成一

41、个有序序列的过程。,基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，直至得到一个长度为n的有序序列为止。,二路归并排序,需解决的关键问题?,如何将两个有序序列合成一个有序序列？怎样完成一趟归并？如何控制二路归并的结束？,8.5归并排序,关键问题：怎样完成一趟归并？,60 20 31 5 44 55 65,8.5归并排序,关键问题：如何将两个有序序列合成一个有序序列？,8.5归并排序,60 20 31 5 44 55 65,5,20,31,60,归并排序练习,12 5 9 20

42、 6 31 24,初始序列,第一趟排序:5 12 9 20 6 31 24,第二趟排序:5 9 12 20 6 24 31,第三趟排序:5 6 9 12 20 24 31,8.5归并排序,二路归并排序算法的性能分析,时间性能：一趟归并操作是将r1rn中相邻的长度为h的有序序列进行两两归并，并把结果存放到r11r1n中，这需要O(n)时间。整个归并排序需要进行 趟，因此，总的时间代价是O(nlog2n)。这是归并排序算法的最好、最坏、平均的时间性能。空间性能：算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为O(n)。,8.5归并排序,8.6各种排序方法的比较,对排序算法应

43、该从以下几个方面综合考虑：时间复杂性；空间复杂性；稳定性；算法简单性；待排序记录个数n的大小；记录本身信息量的大小；关键码的分布情况。,时间复杂度比较,8.6各种排序方法的比较,稳定性比较,所有排序方法可分为两类，（1）一类是稳定的，包括直接插入排序、起泡排序和归并排序；（2）另一类是不稳定的，包括希尔排序、快速排序和堆排序，直接选择排序。,8.6各种排序方法的比较,空间复杂度比较,8.6各种排序方法的比较,算法简单性比较,从算法简单性看，（1）一类是简单算法，包括直接插入排序、直接选择排序和起泡排序，（2）另一类是改进后的算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法都很复杂。,8.6各种排序方法的比较,