北邮数据结构排序课件ppt.ppt

第八章第八章 排序排序北京邮电大学北京邮电大学信息与通信工程学院信息与通信工程学院数据结构与数据结构与STL第八章第八章 排序排序学习内容：学习内容： 1. 1. 概述概述 2. 2. 插入排序插入排序 3. 3. 交换排序交换排序 4. 4. 选择排序选择排序 5. 5. 归并排序归并排序6. 6. 排序比较排序比较7. 7. 外部排序外部排序8. STL 8. STL 中相关排序算法中相关排序算法2022-7-2821. 1. 概述概述数据结构与STL1 1 概述概述排序排序 给定一个记录序列，按照每个记录的关键码将给定一个记录序列，按照每个记录的关键码将记录进行重新排列，使关键码从小到大记录进行重新排列，使关键码从小到大/ /从大从大到小有序。到小有序。正序：关键码从小到大排列正序：关键码从小到大排列逆序：关键码从大到小排列逆序：关键码从大到小排列2022-7-283数据结构与STL1 1 概述概述趟趟 在排序算法中，将待排序的记录扫描一遍称为一在排序算法中，将待排序的记录扫描一遍称为一趟。趟。稳定性稳定性 待排序记录中具有相同关键码的记录，若排序前待排序记录中具有相同关键码的记录，若排序前后，这些记录的相对位置不变，则为稳定排序；后，这些记录的相对位置不变，则为稳定排序；否则为不稳定。否则为不稳定。2022-7-284数据结构与STL1 1 概述概述排序的分类排序的分类 根据是否将全部记录放进内存，分为内部排序根据是否将全部记录放进内存，分为内部排序和外部排序和外部排序 根据排序的原则，可以将排序分成：根据排序的原则，可以将排序分成： 插入排序 交换排序 选择排序 归并排序2022-7-285数据结构与STL1 1 概述概述如何评价一个排序算法？如何评价一个排序算法？排序的基本操作排序的基本操作: :比较和移动比较和移动主要主要: :比较的次数或移动次数较少的算法性能较好。比较的次数或移动次数较少的算法性能较好。次要次要: :空间复杂度空间复杂度. . 算法本身的复杂度算法本身的复杂度2022-7-286数据结构与STL第八章第八章 排序排序学习内容：学习内容： 1. 1. 概述概述 2. 2. 插入排序插入排序 3. 3. 交换排序交换排序 4. 4. 选择排序选择排序 5. 5. 归并排序归并排序6. 6. 排序比较排序比较7. 7. 外部排序外部排序8. STL 8. STL 中相关排序算法中相关排序算法2022-7-2872. 2. 插入排序插入排序数据结构与STL插入排序插入排序主要内容主要内容1 1存储结构存储结构2 2直接插入排序直接插入排序3 3希尔排序希尔排序2022-7-288数据结构与STL1 1存储结构存储结构排序使用顺序结构排序使用顺序结构 为了关注排序算法本身，所以本章所有排序的存为了关注排序算法本身，所以本章所有排序的存储结构是储结构是0 0号位置留空的整型一维数组。号位置留空的整型一维数组。 int rn;2022-7-289数据结构与STL2.2. 插入排序插入排序插入排序的特征插入排序的特征类似于玩纸牌时整理手中纸牌的过程。类似于玩纸牌时整理手中纸牌的过程。寻找一个指定记录在待排序记录中的位置，然后寻找一个指定记录在待排序记录中的位置，然后插入的排序算法。插入的排序算法。2022-7-2810数据结构与STL2.2.直接插入排序直接插入排序基本思想基本思想 每次将一个待排序的记录按其关键码的大小插入每次将一个待排序的记录按其关键码的大小插入到一个已经排序好的有序序列中，直到全部记录到一个已经排序好的有序序列中，直到全部记录排序好。排序好。2022-7-2811数据结构与STLr r1 1rr2 2 r ri-1 i-1 |r|ri i r ri+1 i+1 r rn n有序区无序区插入到合适的位置2.2.直接插入排序直接插入排序需要解决的问题需要解决的问题 1 1）如何构造初始有序序列？）如何构造初始有序序列？ 2 2）如何找到插入的位置？）如何找到插入的位置？2022-7-2812数据结构与STLr r1 1rr2 2 r ri-1 i-1 |r|ri i r ri+1 i+1 r rn n有序区无序区插入到合适的位置1 1）如何构造初始有序序列？）如何构造初始有序序列？2022-7-2813 有序序列r1无序序列 r3.nr2第一趟第一趟 有序序列r1.2无序序列 r4.nr3第二趟第二趟第第n-1n-1趟趟 有序序列r1.n-1rn数据结构与STL 直接插入排序的过程直接插入排序的过程2022-7-2814初始序列初始序列1215 9 20 10 31 24第一趟第一趟12 15 9 20 10 31 24第二趟第二趟9 12 1520 10 31 24第三趟第三趟9 12 15 2010 31 24第四趟第四趟9 10 12 15 20 31 24第五趟第五趟9 10 12 15 20 31 24第六趟第六趟9 10 12 15 20 24 31数据结构与STL2 2）如何找到插入的位置？）如何找到插入的位置？基本思想基本思想 设置设置r0r0为为“哨兵哨兵”，从后向前查找有序区，边，从后向前查找有序区，边查找边后移，直到找到合适的位置，将查找边后移，直到找到合适的位置，将r0r0插入。插入。 2022-7-2815r r1 1rr2 2 r ri-1 i-1 |r|ri i r ri+1 i+1 r rn n有序区无序区插入到合适的位置r0=ri;for (int j=i-1; r0rj; j-) rj+1 =rj; rj+1 = r0;数据结构与STLif (riri-1) r0=ri; for (int j=i-1; r0rj; j-) rj+1 =rj; rj+1 = r0;2. 2. 直接插入排序的算法直接插入排序的算法void InsertSort(int r, int n) /升序排列升序排列 for (int i=2; i=n; i+) /i从从2n循环，共循环，共n-1趟排序趟排序r0=ri; for (int j=i-1; r0rj; j-) rj+1 =rj; rj+1 = r0; 2022-7-2816数据结构与STL2. 2. 直接插入排序的性能分析直接插入排序的性能分析最好情况最好情况正序序列：比较正序序列：比较 移动移动最坏情况最坏情况逆序序列：比较逆序序列：比较 移动移动平均情况平均情况时间复杂度时间复杂度O(nO(n2 2) ) 空间复杂度空间复杂度O(1)O(1) nii2nii2) 1(2022-7-28数据结构与STL17 n-102. 2. 直接插入排序的特点直接插入排序的特点稳定性稳定性插入排序是一种稳定的排序算法插入排序是一种稳定的排序算法适用性适用性 尤其适合待排序记录基本有序的情况尤其适合待排序记录基本有序的情况2022-7-2818数据结构与STL3. 3. 希尔排序希尔排序希尔排序是对插入排序的一种改进希尔排序是对插入排序的一种改进, ,原因原因1)1)基本有序的序列，直接插入最快基本有序的序列，直接插入最快2)2)无序序列，记录数很少时，也很快无序序列，记录数很少时，也很快基本思想基本思想 将待排序的记录集分成多个子集，分别对这些子将待排序的记录集分成多个子集，分别对这些子集进行排序，待整个序列基本有序时，在对记录集进行排序，待整个序列基本有序时，在对记录进行一次直接插入排序。进行一次直接插入排序。2022-7-2819数据结构与STL3.3.希尔排序希尔排序2022-7-2820数据结构与STL49 38 65 97 76 13 27 49 55 04原始序列 d=10/2=513 27 49 55 04 49 38 65 97 76第一趟 d=5/2=23.3.希尔排序希尔排序2022-7-2821数据结构与STL04 27 13 49 38 55 49 65 97 76第二趟第二趟 d=2/2=104 13 27 38 49 49 55 65 76 97第三趟第三趟3.3.希尔排序（缩小增量排序）希尔排序（缩小增量排序）具体排序过程具体排序过程设待排序对象序列有设待排序对象序列有 n 个记录个记录,先取先取 d =1;d=d/2) /以以d为增量为增量 以以d为增量，在子序列中进行插入排序。为增量，在子序列中进行插入排序。2022-7-2823数据结构与STL希尔排序希尔排序假设增量假设增量=d，则一趟希尔排序的过程，则一趟希尔排序的过程for (int i=d+1 ;i=n ; i+) /一趟希尔排序一趟希尔排序 if(ri 0 & r0=1;d=d/2) /以以d为增量为增量 for (int i=d+1 ;i=n ; i+) /一趟希尔排序一趟希尔排序 if(ri 0 & r0rj; j=j-d)rj+d = rj; rj+d = r0; 2022-7-2826数据结构与STL3.3.希尔排序的性能分析希尔排序的性能分析时间复杂度时间复杂度希尔排序的时间与希尔排序的时间与“增量序列增量序列”有关，不同的有关，不同的“增量序列增量序列”时间复杂度不同。时间复杂度不同。经过大量的实验，时间复杂度经过大量的实验，时间复杂度O(n2) 和和 O(nlog2n) 之间之间稳定性稳定性 希尔排序是一种不稳定的排序算法希尔排序是一种不稳定的排序算法2022-7-2827数据结构与STL第八章第八章 排序排序学习内容：学习内容： 1. 1. 概述概述 2. 2. 插入排序插入排序 4. 4. 选择排序选择排序 5. 5. 归并排序归并排序6. 6. 排序比较排序比较7. 7. 外部排序外部排序8. STL 8. STL 中相关排序算法中相关排序算法2022-7-28283. 3. 交换排序交换排序数据结构与STL交换排序交换排序主要内容主要内容 1 1存储结构存储结构 2 2起泡排序起泡排序 3 3起泡排序（改进）起泡排序（改进） 4 4快速排序快速排序 5 5快速排序（改进）快速排序（改进）2022-7-2829数据结构与STL1 1存储结构存储结构排序使用顺序结构排序使用顺序结构 为了关注排序算法本身，所以本章所有排序的存为了关注排序算法本身，所以本章所有排序的存储结构是储结构是0 0号位置留空的整型一维数组。号位置留空的整型一维数组。 int rn;交换排序的特征交换排序的特征 在待排序的记录中选择两个记录，将它们的关在待排序的记录中选择两个记录，将它们的关键码进行比较，如果反序则交换它们的位置。键码进行比较，如果反序则交换它们的位置。2022-7-2830数据结构与STL2. 2. 起泡排序起泡排序基本思想基本思想 两两比较相邻的记录两两比较相邻的记录, ,如果反序如果反序, ,则交换位置则交换位置, ,直直到没有反序的记录为止。到没有反序的记录为止。2022-7-2831无序序列r1.i 有序序列 ri+1.n反序则交换标记数据结构与STL起泡排序的过程起泡排序的过程2022-7-2832第一趟第一趟初始状态初始状态数据结构与STL第二趟第二趟无序区无序区有序区有序区无序区无序区有序区有序区2022-7-2833数据结构与STL2. 2. 起泡排序起泡排序void BubbleSort( int r, int n) /外循环：总共需要遍历的趟数外循环：总共需要遍历的趟数 for (int i=1;in;i+) /n-1趟趟 /内循环：每一趟需要比较的次数内循环：每一趟需要比较的次数for (int j = 1 ; j rj+1) /相邻元素比较相邻元素比较 r0=rj; rj = rj+1; rj+1 = r0; 2022-7-2834数据结构与STL3. 3. 起泡排序（改进）起泡排序（改进）2022-7-28数据结构与STL35初始序列初始序列50 13 55 97 27 38 49 65第一趟第一趟13 50 55 97 27 38 49 6513 50 55 27 97 38 49 6513 50 55 27 38 97 49 6513 50 55 27 38 49 97 6513 50 55 27 38 49 6597pos第二趟第二趟13 50 27 55 38 49 659713 50 27 38 55 49 659713 50 27 38 49 55 65 97pospos=n3. 3. 起泡排序（改进）起泡排序（改进）2022-7-28数据结构与STL36第三趟第三趟13 27 50 38 49 55 65 9713 27 38 50 49 55 65 9713 27 38 49 50 55 65 97pos第四趟第四趟13 27 38 49 50 55 65 97pos3. 3. 起泡排序（改进）起泡排序（改进）具体过程具体过程1）初始状态无序区为）初始状态无序区为r1.n2）对无序区从前向后，依次比较相邻记录，若反）对无序区从前向后，依次比较相邻记录，若反序则交换，并记录交换的位置序则交换，并记录交换的位置pos。最后一次交换。最后一次交换的位置的位置pos，就是下一趟无序区，就是下一趟无序区r1.pos3）反复执行）反复执行2），直到无序区中没有反序的记录），直到无序区中没有反序的记录2022-7-2837数据结构与STL3. 3. 起泡排序（改进）起泡排序（改进）已知无序区已知无序区r1.pos，则如何进行反序交换，则如何进行反序交换?int bound = pos; /带排序记录右边界带排序记录右边界pos=0; /标记，记录交换的位置标记，记录交换的位置 for (int i=1; iri+1) r0 = ri; ri=ri+1; ri+1=r0; pos =i; /记录最后交换的位置记录最后交换的位置 2022-7-2838数据结构与STL3. 3. 起泡排序（改进）起泡排序（改进）void BubbleSort ( int r, int n) int pos = n; while (pos!=0)int bound = pos; /本次无序记录的范围本次无序记录的范围pos = 0;for(int i=1;i ri+1)/ 相邻记录比较相邻记录比较 r0 = ri;ri = ri+1; ri+1=r0; /交换交换pos = i; 2022-7-2839数据结构与STL3.3.起泡排序的性能分析起泡排序的性能分析11)(niin2022-7-2840数据结构与STL最好情况最好情况正序序列：比较 移动最坏情况最坏情况逆序序列：比较 移动平均情况平均情况时间复杂度 O(n2) 空间复杂度 O(1)11)(*3niinn-104.4.快速排序快速排序快速排序是起泡排序的改进快速排序是起泡排序的改进改进着眼点改进着眼点 起泡排序：记录的比较和移动是在相邻位置进行，起泡排序：记录的比较和移动是在相邻位置进行，需要比较移动多次才能到最终的位置。需要比较移动多次才能到最终的位置。 快速排序：记录的比较和移动从两端向中间进行快速排序：记录的比较和移动从两端向中间进行的，记录移动的距离较远。的，记录移动的距离较远。2022-7-2841数据结构与STL4.4.快速排序快速排序快速排序又叫分区交换排序，其基本思想：快速排序又叫分区交换排序，其基本思想：1. 1. 选择一个记录作为轴值，将记录分成选择一个记录作为轴值，将记录分成2 2部分。部分。2. 2. 分别对这两部分重复上述过程。分别对这两部分重复上述过程。2022-7-2842数据结构与STLrr1 1 r r2 2 r ri-1 i-1 r ri i r ri+1 i+1 r ri+2 i+2 r rn n 全部全部=ri 递归递归4.4.快速排序快速排序需要解决的问题需要解决的问题1. 1. 如何选择如何选择基准基准记录？记录？ 记录集中的第一个记录。2. 2. 如何分区，使如何分区，使大于大于基准的记录基准的记录后移后移，小于小于基准基准的记录的记录前移？前移？3. 3. 如何判决快速排序结束？如何判决快速排序结束？ 递归缩小分区，直到分区只有一个记录。2022-7-2843rr1 1 r r2 2rri-1 i-1 r ri i r ri+1 i+1 r ri+2 i+2 r rn n 全部全部=ri 数据结构与STL2. 2. 如何分区？如何分区？分区算法分区算法 初始化初始化 取第一个记录R1作为基准 i 基准左侧待比较的记录， 初始i=1 j 基准右侧待比较的记录, 初始j=n 右侧扫描右侧扫描 从后向前找到第一个比基准小的记录，和基准交换 左侧扫描左侧扫描 从前到后找到第一个比基准大的记录，和基准交换 反复执行，直到反复执行，直到i=ji=j结束结束2022-7-2844数据结构与STL2. 2. 如何分区？如何分区？2022-7-28450 1 2 3 4 50 1 2 3 4 5pivotji数据结构与STL2. 2. 如何分区？如何分区？2022-7-2846一趟快速排序结束，待排序序列被分成两个子序列，再分别进行快速排序。数据结构与STL一趟快速排序一趟快速排序int Partion(int r, int i, int j)int pivot=ri;while (ij)while(i=pivot) j-;rj ri;while(ij) & (ri=pivot) i+;rj ri;return i;2022-7-2847数据结构与STL5 5快速排序（改进）快速排序（改进）改进出发点改进出发点 一趟快速排序：一趟快速排序： 每交换一对记录需要进行三次移动，而实际上排每交换一对记录需要进行三次移动，而实际上排序过程中对序过程中对pivotpivot的位置交换是多余的，只有的位置交换是多余的，只有i=ji=j的位置才是的位置才是pivotpivot的位置。的位置。 所以，可以将所以，可以将pivotpivot保存在保存在r0r0中，排序过程中中，排序过程中只有只有riri和和rjrj移动。移动。2022-7-2848数据结构与STL2 2）分区改进）分区改进分区算法分区算法 初始化初始化 取第一个记录作为基准，保存在任意位置 i 基准左侧待比较的记录， 初始i=1 j 基准右侧待比较的记录, 初始j=n 右侧扫描右侧扫描 从后向前找到第一个比基准小的记录，移至位置i 左侧扫描左侧扫描 从前到后找到第一个比基准大的记录，移至位置j 反复执行，直到反复执行，直到i=ji=j结束，将结束，将r0r0移至移至riri。 2022-7-2849数据结构与STL0 0 1 1 2 2 3 3 4 4 5 5 6 6pivotji2022-7-2850数据结构与STL5 5快速排序（改进）快速排序（改进）2022-7-2851一趟快速排序结束，待排序序列被分成两个子序列，再分别进行快速排序。数据结构与STL一趟快速排序（改进）一趟快速排序（改进）int Partion(int r , int first, int end)int i=first; int j=end; int pivot = ri; /选取基准记录选取基准记录while (ij)while(i=pivot)/右侧扫描右侧扫描 j-;ri + = rj;while(ij) & (ri=pivot) /左侧扫描左侧扫描 i+;rj- =ri;ri = pivot ； return i;2022-7-2852数据结构与STL5 5快速排序（改进）快速排序（改进）2022-7-2853pivotpivot第一趟pivot第二趟第三趟数据结构与STL5.5.快速排序快速排序void Qsort(int r, int i, int j)if ( ij )int pivotloc = Partion(r, i, j); Qsort( r, i, pivotloc-1); Qsort( r, pivotloc+1, j);2022-7-2854数据结构与STL5.5.快速排序的性能分析快速排序的性能分析最好情况最好情况每次划分的左侧序列和右侧序列的长度相同。表每次划分的左侧序列和右侧序列的长度相同。表长为长为n n的序列可划分的序列可划分loglog2 2n n层。层。定位一个记录要对整个待划分序列扫描一遍，所定位一个记录要对整个待划分序列扫描一遍，所需时间需时间O(n)O(n)。 总的时间复杂度总的时间复杂度O(nlogO(nlog2 2n)n)。2022-7-2855n/4n/4n/4n/4n/2n/2n 数据结构与STL5.5.快速排序的性能分析快速排序的性能分析)(2/ ) 1()(211nOnninni2022-7-2856数据结构与STL最坏情况最坏情况待排序记录为逆序或正序，每次划分只得到比上待排序记录为逆序或正序，每次划分只得到比上一次少一个的子序列，此时必须要一次少一个的子序列，此时必须要n-1n-1次递归，次递归，第第i i 次需要次需要n-in-i次比较，所以，总的比较次数：次比较，所以，总的比较次数： 记录的移动次数记录的移动次数=比较次数，所以总的时间复比较次数，所以总的时间复杂度杂度O(nO(n2 2) )5.5.快速排序的性能分析快速排序的性能分析平均性能平均性能时间复杂度时间复杂度O(nlogO(nlog2 2n)n)栈的深度栈的深度O(logO(log2 2n)n)特点特点快速排序是一种不稳定的排序方法快速排序是一种不稳定的排序方法2022-7-2857数据结构与STL第八章第八章 排序排序学习内容：学习内容： 1. 1. 概述概述 2. 2. 插入排序插入排序 3. 3. 交换排序交换排序 4. 4. 选择排序选择排序5. 5. 归并排序归并排序6. 6. 排序比较排序比较7. 7. 外部排序外部排序8. STL 8. STL 中相关排序算法中相关排序算法2022-7-28584. 4. 选择排序选择排序数据结构与STL选择排序选择排序主要内容主要内容 1 1存储结构存储结构 2 2简单选择排序简单选择排序 3 3堆排序堆排序2022-7-2859数据结构与STL1 1存储结构存储结构排序使用顺序结构排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存为了关注排序算法本身，所以本章所有排序的存储结构是储结构是0 0号位置留空的整型一维数组。号位置留空的整型一维数组。 int rn+1; r1,r2,rn r1,r2,rn选择排序的特征选择排序的特征每趟排序在待排序序列中选择关键码最小的记录，每趟排序在待排序序列中选择关键码最小的记录，添加到有序序列中。添加到有序序列中。2022-7-2860数据结构与STL2.2.简单选择排序简单选择排序基本思想基本思想 第第 i i 趟排序在无序序列趟排序在无序序列ri.nri.n 中选择关键码中选择关键码最小的记录，与最小的记录，与riri交换，使有序序列不断增长交换，使有序序列不断增长直到全部排序完毕。直到全部排序完毕。2022-7-2861r r1 1rr2 2 r ri-1 i-1 |r|ri i r ri+1 i+1 rrminmin r rn n有序区无序区交换数据结构与STL2.2.简单选择排序简单选择排序2022-7-2862 49 27 65 97 76 13 38初始化初始化 13 27 65 97 76 49 38第一趟第一趟 13 27 65 97 76 49 38第二趟第二趟如何在ri.n中选择最小的记录？ 13 27 38 97 76 49 65第三趟第三趟 13 27 38 49 76 97 65 第四趟第四趟 13 27 38 49 65 97 76第五趟第五趟 13 27 38 49 65 76 97第六趟第六趟数据结构与STL2.2.简单选择排序简单选择排序1 1）如何在无序区）如何在无序区rri.ni.n 选择最小的记录选择最小的记录? ? 假设无序区的ri是最小记录，附设一个变量index=i,然后依次将后续的记录与rindex比较，如果比rindex小，则index记录该位置。int index = i;/假设index是最小的for(int j=i+1; j=n; j+) /选择最小记录的位置if (rj rindex) index = j 2) 比较完毕，交换比较完毕，交换rindex和和ri的记录。的记录。2022-7-2863indexindex记录无序区记录无序区最小记录的位置最小记录的位置数据结构与STL2.2.简单选择排序简单选择排序void SelectSort(int r, int n)for(int i=1; in; i+) /n-1趟排序趟排序int index = i;/假设假设index是最小的是最小的 for(int j=i+1; j=n; j+)/查找最小记录的位置查找最小记录的位置 if (rj rindex)index = j ;if (index!=i)/若第一个就是最小元素，则不用交换若第一个就是最小元素，则不用交换 r0=ri; ri=rindex; rindex =r0;/利用利用r0作为临时空间交换记录作为临时空间交换记录2022-7-2864数据结构与STL2.2.简单选择排序性能分析简单选择排序性能分析特点特点移动次数最少，稳定的排序算法移动次数最少，稳定的排序算法最好情况最好情况正序序列：比较正序序列：比较移动移动最坏情况最坏情况 序列：比较序列：比较移动移动逆序序列逆序序列- -不是最坏不是最坏 移动移动 平均情况平均情况时间复杂度时间复杂度 O(n2) 空间复杂度空间复杂度O(1)11niin2022-7-28数据结构与STL65011niin3*(n-1)3*(n-1)/23. 3. 堆排序堆排序什么是堆？什么是堆？堆是具有下列性质的完全二叉树：堆是具有下列性质的完全二叉树：小根堆：每个结点的值小根堆：每个结点的值左右孩子结点的值左右孩子结点的值大根堆：每个结点的值大根堆：每个结点的值左右孩子结点的值左右孩子结点的值 k ki i k k2i 2i k ki i k k2i2i k ki i k k2i+12i+1 或或 k ki i k k2i+12i+1 2022-7-2866小根堆大根堆数据结构与STL3. 3. 堆排序堆排序小根堆大根堆小根堆大根堆2022-7-28671015562530707056302515 10( 10, 15, 56, 25, 30, 70 )( 10, 15, 56, 25, 30, 70 )( 70, 56, 30, 25, 15, 10 )( 70, 56, 30, 25, 15, 10 ) 堆的特点：根结点堆的特点：根结点一定是最大或最小者一定是最大或最小者数据结构与STL思考？思考？ 12, 36, 27, 65, 40, 14, 98, 81这个序列是不是这个序列是不是堆？堆？2022-7-28681236276540149881数据结构与STL3. 3. 堆排序堆排序堆调整问题堆调整问题 一棵完全二叉树中，根结点的左右子树都是堆，一棵完全二叉树中，根结点的左右子树都是堆，如何调整根结点，使整棵二叉树成为一个堆？如何调整根结点，使整棵二叉树成为一个堆？2022-7-28694024453276654997数据结构与STL堆调整过程堆调整过程筛选筛选小根堆筛选：小根堆筛选：总是将根结点与左右孩子进行比较，若不满足堆总是将根结点与左右孩子进行比较，若不满足堆的条件，则将的条件，则将根结点根结点与与较小的结点较小的结点交换，一直到交换，一直到叶子结点，或所有子树均为堆为止叶子结点，或所有子树均为堆为止。2022-7-2870402445327665499740243240数据结构与STL筛选算法筛选算法堆的存储结构堆的存储结构顺序存储结构，顺序存储结构，ri是是r2i r2i+1的父结点的父结点前提前提 1）要筛选的结点编号是）要筛选的结点编号是k 2）堆中最后一个结点的编号是）堆中最后一个结点的编号是m 3）结点）结点k的左右子树均为堆（即的左右子树均为堆（即rk+1rm满足满足堆的条件）堆的条件）2022-7-2871数据结构与STL筛选算法筛选算法( (小根堆小根堆) )void Sift (int r, int k, int m) int i=k， j=2*i; /i是要筛选的结点，是要筛选的结点，j是是i的左孩子的左孩子 while (j=m) if ( j rj+1) j+; /j 是左右孩子中较小者是左右孩子中较小者if (ri=1; i- )Sift ( r, i, n );2022-7-2875493865977613274949 38 65 97 76 13 27 4949976513134913 38 27 49 76 65 49 974927数据结构与STL4. 4. 堆排序堆排序如何输出堆顶元素？如何输出堆顶元素？将堆顶元素和最后一个元素交换将堆顶元素和最后一个元素交换如何将剩余元素调整成堆？如何将剩余元素调整成堆？ 1)需要输出堆顶元素需要输出堆顶元素n-1次次 2)则第则第i次，需要调整的元素范围次，需要调整的元素范围r1.n-i2022-7-2876数据结构与STL4. 4. 堆排序堆排序筛选（小根堆）筛选（小根堆）r1 rn;Sift ( r, 1, n-1 ); 2022-7-2877133827497665499713972797499713 38 27 49 76 65 49 9727 38 49 49 76 65 97 13输出堆顶元素数据结构与STL4. 4. 堆排序堆排序筛选（小根堆）筛选（小根堆）r1 rn-1;Sift ( r, 1, n-2);2022-7-28782738494976659713972797493827 38 49 49 76 65 97 13输出堆顶元素38 49 49 97 76 65 27 1397数据结构与STL4. 4. 堆排序堆排序筛选（小根堆）筛选（小根堆）r1 rn-2;Sift ( r, 1, n-3);2022-7-2879输出堆顶元素38 49 49 97 76 65 27 133849499776659713276538496549 65 49 97 76 38 27 13数据结构与STL4. 4. 堆排序堆排序筛选（小根堆）筛选（小根堆）r1 rn-i+1;Sift ( r, 1, n-i);2022-7-288049654997769713273849 65 49 97 76 38 27 13输出堆顶元素数据结构与STL4. 4. 堆排序堆排序算法算法void Sift (int r, int k, int m) int i=k， j=2*i; /i是要筛选的结点，是要筛选的结点，j是是i的左孩子的左孩子 while (j=m) if ( j rj+1) j+; /j 是左右孩子中较小者是左右孩子中较小者 if (rirj) break; /符合小根堆的条件，结束符合小根堆的条件，结束 else rirj ; /根结点与孩子结点交换根结点与孩子结点交换 i = j; j= 2*i; 2022-7-2881数据结构与STL4. 4. 堆排序性能分析堆排序性能分析堆排序的时间消耗堆排序的时间消耗1. 1. 建堆建堆 时间复杂度O(nlog2n)2. 2. 重建堆时的筛选重建堆时的筛选第i次输出堆顶记录重建堆的时间为O(log2(n-i)，需要n-1次输出堆顶元素。总的是间复杂度总的是间复杂度O(nlogO(nlog2 2n)n)堆排序是一种不稳定的排序方法。堆排序是一种不稳定的排序方法。2022-7-2882数据结构与STL第八章第八章 排序排序学习内容：学习内容： 1. 1. 概述概述 2. 2. 插入排序插入排序 3. 3. 交换排序交换排序 4. 4. 选择排序选择排序 5. 5. 归并排序归并排序6. 6. 排序比较排序比较7. 7. 外部排序外部排序8. STL 8. STL 中相关排序算法中相关排序算法2022-7-28835. 5. 归并排序归并排序数据结构与STL归并排序归并排序主要内容主要内容 1 1存储结构存储结构 2 2二路归并排序（非递归）二路归并排序（非递归） 3 3二路归并排序（递归）二路归并排序（递归）2022-7-2884数据结构与STL1 1存储结构存储结构排序使用顺序结构排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存为了关注排序算法本身，所以本章所有排序的存储结构是储结构是0 0号位置留空的整型一维数组。号位置留空的整型一维数组。 int rn;归并排序的特征归并排序的特征将两个或两个以上的有序序列归并成一个有序序将两个或两个以上的有序序列归并成一个有序序列的过程。列的过程。2022-7-2885数据结构与STL归并排序归并排序最简单的归并排序最简单的归并排序两路归并排序两路归并排序1 1）将）将n n个记录的序列分成个记录的序列分成n n个子集个子集 2 2）将相邻的两个子合并成）将相邻的两个子合并成n/2n/2个子集个子集3 3）将相邻的两个子合并成）将相邻的两个子合并成n/4n/4个子集个子集合并成一个子集。合并成一个子集。2022-7-2886数据结构与STL2.2.二路归并排序二路归并排序初始序列初始序列 (49) (38) (65) (97) (76) (13) (27)(49) (38) (65) (97) (76) (13) (27)2022-7-2887(38 49) (65 97) (13 76) 27(38 49 65 97) (13 27 76)(13 27 38 49 65 76 97)一趟二趟三趟数据结构与STL2.2.二路归并排序二路归并排序1.如何构造初始序列？如何构造初始序列？将整个序列看成是长度为将整个序列看成是长度为1的的n个有序序列个有序序列2.如何将相邻序列归并在一起？如何将相邻序列归并在一起？相邻序列相邻序列rsrm和和rm+1rt，归并成一个新，归并成一个新序列序列r1sr1t。 2022-7-2888rm+1 rt，rs rm，r1s r1t，有序序列有序序列有序序列有序序列 数据结构与STL归并一次归并一次void Merge (int r, int r1, int s, int m, int t) int i=s; /i指向指向rsm int j=m+1; /j指向指向rm+1t, int k=s; /k指向指向r1; while (i=m & j=t) if (rirj) r1k+ = ri+; /取取ri和和 rj中较小者放入中较小者放入r1k，并且自加，并且自加1 else r1k+ = rj+; 2022-7-2889rm+1 rt，rs rm，r1s r1t，有序序列有序序列有序序列有序序列数据结构与STL归并一次归并一次 if (i=m) /若若rsm没处理完没处理完 while (i=m) r1k+= ri+; if (j=t) /若若rm+1t没处理完没处理完 while (j=t) r1k+= rj+;2022-7-2890rm+1 rt，rs rm，r1s r1t，有序序列有序序列有序序列有序序列数据结构与STL2.2.一趟归并（非递归）一趟归并（非递归）1.1.分析分析 除最后一个序列外，其他序列的长度相同，用除最后一个序列外，其他序列的长度相同，用h h表表示示把若干个长度为把若干个长度为h h的序列和最后一个的序列和最后一个=h=h的序列两的序列两两归并，把结果保存在两归并，把结果保存在r11.nr11.n中中2022-7-2891hhhh1nii数据结构与STL2.2.一趟归并（非递归）一趟归并（非递归）三种情况三种情况 2022-7-2892hhhh1niin-h+1hhhh1niihin-h+1hhhhh1niii=n-2h+1数据结构与STL2.2.一趟归并的算法（非递归）一趟归并的算法（非递归）void MergePass(int r,int