《第9章 排序(精品).ppt》由会员分享，可在线阅读，更多相关《第9章 排序(精品).ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、安安徽徽理理工工大大学学第第9 9章章 排排 序序v 理解和熟悉各种内部排序的基本思想和过程；理解和熟悉各种内部排序的基本思想和过程；v 掌握内部排序算法的时间复杂度的分析方法和结论；掌握内部排序算法的时间复杂度的分析方法和结论；v 要要求求能能根根据据各各种种内内部部排排序序方方法法的的优优缺缺点点及及不不同同场场合合选选择择合适的排序方法。合适的排序方法。学习要点学习要点安安徽徽理理工工大大学学9.1 基本概念基本概念排序：排序：设含有设含有n个记录的文件个记录的文件r1,r2,.,rn，其相应的关键字其相应的关键字为为 K1，K2，.，Kn，将记录按关键字值非递减（或非递增）将记录按关键
2、字值非递减（或非递增）顺序排列的过程，称为排序。顺序排列的过程，称为排序。对所有的对所有的Ki=Kj（ij），），若排序前若排序前Ri领先于领先于Rj，排序后排序后Ri仍领先于仍领先于Rj，则称该排序方法是则称该排序方法是稳定的稳定的，反之，称为，反之，称为不稳定的不稳定的。内部排序：内部排序：待排序文件的全部记录存放在内存进行的排序，称待排序文件的全部记录存放在内存进行的排序，称为内部排序。为内部排序。外外部部排排序序：排排序序过过程程中中需需要要进进行行内内外外存存数数据据交交换换的的排排序序，称称为为外部排序。外部排序。安安徽徽理理工工大大学学在排序过程中，通常进行两种基本操作：在排序过
3、程中，通常进行两种基本操作：（1）比较比较两个关键字大小；两个关键字大小；（2）将记录从一个位置）将记录从一个位置移动移动到另一个位置。到另一个位置。约定：约定：v 待排序的一组记录存放在地址连续的一组存储单元中，它类待排序的一组记录存放在地址连续的一组存储单元中，它类似于线性表的顺序存储结构。似于线性表的顺序存储结构。v 待排的记录的数据类型定义如下：待排的记录的数据类型定义如下：typedef struct KeyType key;OtherType other;DataType;typedef struct DataType rMAXSIZE+1;int length;SqList;9.
4、1 基本概念基本概念安安徽徽理理工工大大学学9.2 插入排序插入排序v 插入排序的基本方法是插入排序的基本方法是:将待排序文件中的记录，将待排序文件中的记录，逐个地按其排序码值的大小插入到逐个地按其排序码值的大小插入到目前已经排好序的若干个记录组成的文件中的适当位置，并保持目前已经排好序的若干个记录组成的文件中的适当位置，并保持新文件有序。新文件有序。安安徽徽理理工工大大学学9.2.1 直接插入排序直接插入排序基本思想：将一个记录插入到已排好序的有序表中，得到一个新基本思想：将一个记录插入到已排好序的有序表中，得到一个新的、记录数增的、记录数增1的有序表。的有序表。例如：已知待排序的一组记录为
5、例如：已知待排序的一组记录为49、38、65、97、76、13、27。假设在排序过程中，前假设在排序过程中，前4个记录已按关键字递增的次序重新排列，个记录已按关键字递增的次序重新排列，构成一个含构成一个含4个记录的有序序列个记录的有序序列38，49，65，97，现要将关键，现要将关键字为字为76的记录插入该序列中，则按从后向前的顺序对该序列进行的记录插入该序列中，则按从后向前的顺序对该序列进行查找，由于查找，由于65 76 97，则，则76应插入到应插入到65和和97之间，从而得到之间，从而得到新的有序序列新的有序序列 38，49，65，76，97，称该过程为，称该过程为一趟直接插一趟直接插入
6、排序入排序。安安徽徽理理工工大大学学q 直接插入排序方法直接插入排序方法方法：将序列中的第一个记录看成是一个有序的子序列，从第方法：将序列中的第一个记录看成是一个有序的子序列，从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。有序序列为止。void insertsort(SqList *S)for(i=2;ilength;i+)S-r0=S-ri;j=i-1;while(S-r0.keyrj.key)S-rj+1=S-rj;j-;S-rj+1=S-r0;安安徽徽理理工工大大学学S.r0 初始关键字初始关键字：(49)3
7、8 65 97 76 13 27 49*i=2：(38)(38 49)65 97 76 13 27 49*i=3：(65)(38 49 65)97 76 13 27 49*i=4：(97)(38 49 65 97)76 13 27 49*i=5：(76)(38 49 65 76 97)13 27 49*i=6：(13)(13 38 49 65 76 97)27 49*i=7：(27)(13 27 38 49 65 76 97)49*i=8：(49)(13 27 48 49 49*65 76 97)q 直接插入排序示例直接插入排序示例安安徽徽理理工工大大学学 对对于于排排序序的的效效率率分分析析
8、，主主要要从从比比较较次次数数和和移移动动次次数数两两方面着手。方面着手。直直接接插插入入排排序序的的效效率率与与待待排排文文件件的的关关键键字字排排列列有有关关，最好情况为最好情况为O(n)，最坏情况为最坏情况为O(n2)。直接插入排序的平均时间复杂度为直接插入排序的平均时间复杂度为O(n2)。直接插入排序是稳定的。直接插入排序是稳定的。q 直接插入排序效率分析直接插入排序效率分析安安徽徽理理工工大大学学基本思想基本思想：设在顺序表中有一：设在顺序表中有一 个对象序列个对象序列 V1,V2,Vn。其中其中,V1,V2,Vi-1 是已经排好序的对是已经排好序的对象。在插入象。在插入Vi 时时,
9、利用折半查找方法寻找利用折半查找方法寻找Vi 的插入位的插入位置。置。9.2.2 折半插入排序折半插入排序安安徽徽理理工工大大学学void BinaryInsertSort(SqList*s)for(i=2;ilength;i+)s-r0=s-ri;low=1;high=i-1;while(lowr0.keys-rmid.key)low=mid+1;else high=mid-1;for(j=i-1;j=high;j-)s-rj+1=s-rj;s-rhigh+1=s-r0;和直接插入排序相比，和直接插入排序相比，折半插入排序仅减少了折半插入排序仅减少了比较次数，而记录的移比较次数，而记录的移动
10、次不变。其时间复杂动次不变。其时间复杂度仍为度仍为O(n2)。q 折半插入排序算法折半插入排序算法安安徽徽理理工工大大学学 基本思想：希尔排序（基本思想：希尔排序（Shell Sort）又称为又称为“缩小增量排序缩小增量排序”。先将整个待排元素序列分割成若干个子序列（由相隔某个先将整个待排元素序列分割成若干个子序列（由相隔某个“增增量量”的元素组成的）分别进行直接插入排序，待整个序列中的的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。插入排序。1.若待排序文件若待排序文件基本
11、有序基本有序，即文件中具有特性：，即文件中具有特性：ri.keyMaxrj（其其中中1ji）的的记记录录数数较较少少，则则文文件件中中大多数记录都不需要进行插入。大多数记录都不需要进行插入。2.基本有序时，直接插入排序效率可以提高，接近于基本有序时，直接插入排序效率可以提高，接近于O(n)。9.2.3 希尔排序希尔排序安安徽徽理理工工大大学学例如，例如，n=8，数组数组R的八个元素分别为：的八个元素分别为：17，3，30，25，14，17*，20，9。下面给出希尔排序算法的执行过程。下面给出希尔排序算法的执行过程。初始状态：初始状态：d=4 17 3 30 25 14 17*20 9第一趟结果
12、：第一趟结果：d=2 14 3 20 9 17 17*30 25第二趟结果：第二趟结果：d=1 14 3 17 9 20 17*30 35第三趟结果：第三趟结果：3 9 14 17 17*20 30 35q 希尔排序示例希尔排序示例安安徽徽理理工工大大学学void ShellInsert(SqList*s,int gap)for(i=gap+1;iri.keyri-gap.key)s-r0=s-ri;for(j=i-gap;j0&s-r0.keyrj.key);j-=gap)s-rj+gap=s-rj;s-rj+gap=s-r0;void ShellSort(SqList*s,int gaps
13、,int t)for(int k=0;kt;k+)ShellInsert(s,gapsk);q 希尔排序算法希尔排序算法安安徽徽理理工工大大学学v 对希尔排序的分析提出了许多困难的数学问题，特别是如何对希尔排序的分析提出了许多困难的数学问题，特别是如何选择增量序列才能产生最好的排序效果，至今没有得到解决。选择增量序列才能产生最好的排序效果，至今没有得到解决。为什么希尔排序的时间性能优于直接插入排序呢？当文件为什么希尔排序的时间性能优于直接插入排序呢？当文件初基本有序时直接插入排序所需的比较和移动次数均较少。另初基本有序时直接插入排序所需的比较和移动次数均较少。另一面，当一面，当n值较小时，值较
14、小时，n和和n2的差别也较小，即直接插入排序的的差别也较小，即直接插入排序的最好时间复杂度最好时间复杂度O(n)和最坏时间复杂度和最坏时间复杂度O(n2)差别不大。在希尔差别不大。在希尔排序时增量较大，分组较多，每组的记录数目少，故各组内直排序时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于文件较近于有序状态，所以新的的记录数目逐渐增多，但由于文件较近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接接入排一趟排序过程也较快。因此，希尔排序在
15、效率上较直接接入排序有较大的改进。它的时间复杂度为序有较大的改进。它的时间复杂度为O(n1.3)。q 希尔排序性能分析希尔排序性能分析安安徽徽理理工工大大学学1.子文件（子序列）的构成不是简单地子文件（子序列）的构成不是简单地“逐段分割逐段分割”，而是将，而是将相隔某个相隔某个“增量增量”的记录组成一个子文件。的记录组成一个子文件。2.增量序列应是递减，且最后一个必须为增量序列应是递减，且最后一个必须为1。3.希尔排序法是不稳定的（由于希尔排序对每个子序列单独比希尔排序法是不稳定的（由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同关键字元素的原较，在比较时进行元素移动，有
16、可能改变相同关键字元素的原始顺序，因此希尔排序是不稳定的）。始顺序，因此希尔排序是不稳定的）。q 希尔排序特点希尔排序特点安安徽徽理理工工大大学学9.3 交换排序交换排序9.3.1 冒泡排序冒泡排序基本思想：基本思想：首先将第一个记录的关键字和第二个记录的关键首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第二个记录和第三个记录的关键字。依次类推，直至第n-1个记个记录和第录和第n个记录的关键字进行过比较为止。上述过程称作第个记录的关键字进行过比较为止。
17、上述过程称作第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序，对前一个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记个记录进行同样操作，其结果使得关键字次大的记录被安置到第录进行同样操作，其结果使得关键字次大的记录被安置到第n-1个记录的位置上。如此进行下去。判别冒泡排序结束条件个记录的位置上。如此进行下去。判别冒泡排序结束条件是：是：在一趟排序过程中没有进行过交换记录的操作。在一趟排序过程中没有进行过交换记录的操作。安安徽徽理理工工大大学学初始关键字：初始关键字：49 38 65 97 7
18、6 13 27 49第一趟排序后：第一趟排序后：38 49 65 76 13 27 49 97第二趟排序后：第二趟排序后：38 49 65 13 27 49 76第三趟排序后：第三趟排序后：38 49 13 27 49 65第四趟排序后：第四趟排序后：38 13 27 49 49第五趟排序后：第五趟排序后：13 27 38 49第六趟排序后：第六趟排序后：13 27 38q 冒泡排序示例冒泡排序示例安安徽徽理理工工大大学学void BubbleSort(SqList*s)int i,j;for(i=1;ilength-1;i+)for(j=2;ilength-i;j+)if(s-rj.keyr
19、j-1.key)s-r0=s-rj;s-rj=s-rj-1;s-rj-1=s-r0;q 冒泡排序算法冒泡排序算法(1)安安徽徽理理工工大大学学void BubbleSort(SqList*s)int i,j,tag;j=s-length-1;do tag=1;for(i=1;iri+1.keyri.key)s-r0=s-ri+1;s-ri+1=s-ri;s-ri=s-r0;tag=0;if(!tag)j-;while(!tag&j);return;q 冒泡排序算法冒泡排序算法(2)安安徽徽理理工工大大学学 在对象的初始排列已经按关键字从小到大排好序时，此算法在对象的初始排列已经按关键字从小到大
20、排好序时，此算法只执行一趟冒泡，做只执行一趟冒泡，做 n-1 次关键字比较，不移动对象。这是最次关键字比较，不移动对象。这是最好的情形。好的情形。最坏的情形是算法执行了最坏的情形是算法执行了n-1趟冒泡，第趟冒泡，第 i 趟趟(1 in)做做了了 n-i 次关键字比较，执行了次关键字比较，执行了n-i 次对象交换。总的时间复杂度次对象交换。总的时间复杂度为为O(n2)。冒泡排序是一个稳定的排序方法。冒泡排序是一个稳定的排序方法。q 冒泡排序算法分析冒泡排序算法分析安安徽徽理理工工大大学学v 基本思想：基本思想：通过一趟排序将待排记录分割成独立的两部分，通过一趟排序将待排记录分割成独立的两部分，
21、其中一部分记录的关键字均比另一部分记录的关键字小，则可其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。分别对这两部分记录继续进行排序，以达到整个序列有序。v 一趟快速排序：一趟快速排序：首先选取一个记录（通常选取第一个记录）首先选取一个记录（通常选取第一个记录）作为界点，然后将所有关键字较它小的记录都安置在它的位置作为界点，然后将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由之前，将所有关键字较它大的记录都安置在它的位置之后。由此以该此以该“界点界点”记录最后所落的位置记录最后所落的位置i为
22、分界线，将整个序列分为分界线，将整个序列分割成两个子序列。割成两个子序列。然后分别对这两个子序列重复施行上述方法，直到所有的然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。对象都排在相应位置上为止。9.3.2 快速排序快速排序安安徽徽理理工工大大学学v 附设两个指针附设两个指针low和和high，其初值分别指向数组的单元其初值分别指向数组的单元1和单和单元元n。选择第一个记录为界点，其关键字为选择第一个记录为界点，其关键字为pivotkey。将。将pivotkey复制到复制到r0中，从中，从high所指的位置起向前搜索找到第一所指的位置起向前搜索找到第一个关键字小于
23、个关键字小于pivotkey的记录复制到的记录复制到low所指位置中，然后从所指位置中，然后从low所指位置起向后搜索，找到第一个关键字大于所指位置起向后搜索，找到第一个关键字大于pivotkey的记的记录复制到录复制到high所指位置中，重复这两步直到所指位置中，重复这两步直到lowhigh为止。为止。v快速排序是对冒泡排序的一种改进方法，算法中元素的比较和快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，关键字较大的元素一次就能够交交换是从两端向中间进行的，关键字较大的元素一次就能够交换到后面单元，关键字较小的记录一次就能够交换到前面单元，换到后面单元，关键字
24、较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。记录每次移动的距离较远，因而总的比较和移动次数较少。q 具体做法具体做法安安徽徽理理工工大大学学 0 1 2 3 4 5 6 7 827386597761349*第一次交换第一次交换lowhigh49 0 1 2 3 4 5 6 7 827389776136549*第二次交换第二次交换lowhigh49q 具体实现过程具体实现过程 0 1 2 3 4 5 6 7 838659776132749*初始关键字初始关键字pivotkeylowhigh49安安徽徽理理工工大大学学 0 1 2 3 4 5 6 7 8
25、27381397766549*第三次交换第三次交换lowhigh49 0 1 2 3 4 5 6 7 827381376976549*第四次交换第四次交换lowhigh49 0 1 2 3 4 5 6 7 827381376976549*第一趟完成第一趟完成low high49q 具体实现过程具体实现过程 0 1 2 3 4 5 6 7 827389776136549*第二次交换第二次交换lowhigh4949安安徽徽理理工工大大学学q 快速排序全过程快速排序全过程 初始状态初始状态 49 38 65 97 76 13 27 49 一趟快速排序后一趟快速排序后 27 38 13 49 76 9
26、7 65 49 分别进行快速排序分别进行快速排序 13 27 38 结束结束结束结束 49 65 76 97 49 65 结束结束结束结束 有序序列有序序列 13 27 38 49 49 65 76 97 整个快速排序过程可整个快速排序过程可递归进行递归进行安安徽徽理理工工大大学学 int QuickSort1(SqList*s,int low,int high)KeyType pivotkey;s-r0=s-rlow;pivotkey=s-rlow.key;while(low high)while(lowrhigh.key=pivotkey)high-;s-rlow=s-rhigh;whil
27、e(lowrlow.key rhigh=s-rlow;s-rlow=s-r0;return low;q 一趟快速排序算法实现一趟快速排序算法实现安安徽徽理理工工大大学学void QuickSort(SqList*s,int low,int high)int pivotloc;if(low high)pivotloc=Quicksort1(s,low,high);QuickSort(s,low,pivotloc-1);QuickSort(s,pivotloc+1,high);q 递归形式的快速排序算法递归形式的快速排序算法安安徽徽理理工工大大学学v 从从时时间间上上看看，快快速速排排序序平平均均
28、计计算算时时间间是是O(nlog2n)。实实验验结结果果表表明明:就就平平均均计计算算时时间间而而言言,快快速速排排序序是是所所有有内内排排序序方方法法中中最最好好的的一一个个。在在最最坏坏的的情情况况,即即待待排排序序对对象象序序列列已已经经按按其其排排序序码码从从小小到到大大排排好好序序的的情情况况下下，其其时时间间复复杂杂度度为为O(n2)。v 从从空空间间上上看看，快快速速排排序序是是递递归归的的，最最大大递递归归调调用用层层次次数数与与递递归归树树的的高高度度一一致致，理理想想情情况况为为 log2(n+1)。因因此此，要求存储开销为要求存储开销为 O(log2n)。v 快速排序是一
29、种不稳定的排序方法。快速排序是一种不稳定的排序方法。q 算法分析算法分析安安徽徽理理工工大大学学9.4 选择排序选择排序选择排序的基本思想是：选择排序的基本思想是：每一趟每一趟(例如第例如第 i 趟，趟，i=1,n-1)在后面的在后面的 n-i+1 个待排序对象中选出关键字最小的对象个待排序对象中选出关键字最小的对象,作为有序对象序作为有序对象序列的第列的第 i 个对象。待到第个对象。待到第 n-1 趟作完，待排序对象只剩下趟作完，待排序对象只剩下1个，就不用再选了。个，就不用再选了。安安徽徽理理工工大大学学9.4.1 简单选择排序简单选择排序v 基本步骤为：基本步骤为：i从从1开始，直到开始
30、，直到n-1，进行进行n-1趟排序，第趟排序，第i 趟的趟的排序过程为：排序过程为：在一组对象在一组对象rirn（i=1,2,n-1）中选择具有中选择具有最小关键字的对象，并和第最小关键字的对象，并和第 i 个对象进行交换。个对象进行交换。void SelectSort(SqList*s)for(i=1;i length;i+)for(j=i+1,t=I;jlength;j+)if(s-rt.keys-r)L.ri L.rj;/SelectSort安安徽徽理理工工大大学学q 算法分析算法分析v 直接选择排序的比较次数与对象的初始排列无关。设整个待排直接选择排序的比较次数与对象的初始排列无关。设
31、整个待排序对象序列有序对象序列有 n 个对象个对象,则第则第 i 趟选择具有最小排序码对象所趟选择具有最小排序码对象所需的比较次数总是需的比较次数总是 n-i-1 次。总的排序码比较次数为次。总的排序码比较次数为n(n-1)/2。v 对象的移动次数与对象序列的初始排列有关。当这组对象的初对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其排序码从小到大有序的时候始状态是按其排序码从小到大有序的时候,对象的移动次数为对象的移动次数为0，达到最少。达到最少。v 最坏情况是每一趟都要进行交换，总的对象移动次数为最坏情况是每一趟都要进行交换，总的对象移动次数为 3(n-1)。v 直接选择
32、排序是一种不稳定的排序方法。直接选择排序是一种不稳定的排序方法。安安徽徽理理工工大大学学9.4.2 堆排序堆排序堆的定义：堆的定义：n个元素的序列个元素的序列 k1，k2，kn，当且仅当满当且仅当满足以下关系时：足以下关系时：ki k2i ki k2i ki k2i+1 ki k2i+1 其其中中i=1，2，n/2，则则称称此此n个个元元素素的的关关键键字字k1，k2，kn为一个堆。为一个堆。解释：如果让满足以上条件的元素序列解释：如果让满足以上条件的元素序列 k1，k2，kn 顺次排成一棵完全二叉树，则此树的特点是：顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左
33、右孩子，此树的根树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。结点（即堆顶）必最大（或最小）。或或安安徽徽理理工工大大学学q 大大根堆和小根堆根堆和小根堆（a）小根堆小根堆 （b）大根堆大根堆09651723 45 78 87533187537845 65 09 311723（09,17,65,23,45,78,87,53,31）（87,78,53,45,65,09,31,17,23）安安徽徽理理工工大大学学 以初始关键字序列，建立堆；以初始关键字序列，建立堆；输出堆顶元素；输出堆顶元素；调整余下的元素，使其成为一个新堆；调整余下的元素，使其成为一个新堆；
34、重复重复、n 次，得到次，得到 一个有序序列。一个有序序列。关键要解决关键要解决和和，即：，即：如何由一个无序序列如何由一个无序序列建成一个堆？建成一个堆？如何在输出堆顶元素如何在输出堆顶元素之后调整剩余元素成之后调整剩余元素成为一个新的堆？为一个新的堆？q 堆排序基本思想堆排序基本思想安安徽徽理理工工大大学学v 调整方法调整方法（以小根堆为例）（以小根堆为例）13273849 76 65 499797273849 76 65 491327973849 76 65 491327493849 76 65 9713 将堆顶元素和堆的最后一个元素位置交换；将堆顶元素和堆的最后一个元素位置交换；然后以
35、当前堆顶元素和其左、右子树的根结然后以当前堆顶元素和其左、右子树的根结点进行比较（此时，左、右子树均为堆），并点进行比较（此时，左、右子树均为堆），并与值较小的结点进行交换；与值较小的结点进行交换；重复重复，继续调整被交换过的子树，直到叶，继续调整被交换过的子树，直到叶结点或没进行交换为止。称这个调整过程为结点或没进行交换为止。称这个调整过程为筛筛选选。安安徽徽理理工工大大学学void HeapAdjust(SqList*s，int n，int m)int i,j;DataType rc;rc=s-rn;i=n;for(j=2*i；j=m；j*=2)if(jrj.keyrj+1.key)j+；
36、if(rc.keys-rj.key)break；i=j;s-ri=rc;v 筛选算法筛选算法安安徽徽理理工工大大学学v 无序序列建立堆无序序列建立堆49653897 76 13 2749*方法：方法：从完全二叉树的最后一个非终端结点从完全二叉树的最后一个非终端结点 n/2开始（所有大于开始（所有大于 n/2的的 结点都是叶子结点，以这结点都是叶子结点，以这些结点为根的子树均已是堆），反复调用筛选过程，些结点为根的子树均已是堆），反复调用筛选过程，直到第一个结点，则得到一个堆。直到第一个结点，则得到一个堆。例：（例：（49，38，65，97，76，13，27，49*）。）。49653849*76
37、 13 279749133849*76 65 279713493849*76 65 279713273849*76 65 4997安安徽徽理理工工大大学学void HeapSort(SqList*s)for(i=s-length/2;i0;i-)HeapAdjust(s，i，s-length);for(i=s-length；i1；i-)s-r1s-ri;HeapAdjust(s，1，i-1);v 堆排序算法堆排序算法安安徽徽理理工工大大学学 在整个堆排序中，共需要进行在整个堆排序中，共需要进行n/2+n-1次筛选运算，每次筛次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的关键字的比较和移动次
38、数选运算进行双亲和孩子或兄弟结点的关键字的比较和移动次数都不会超过完全二叉树的深度，所以，每次筛选运算的时间复都不会超过完全二叉树的深度，所以，每次筛选运算的时间复杂度为杂度为O(log2n)，故整个堆排序过程的时间复杂度为故整个堆排序过程的时间复杂度为O(nlog2n)。堆排序不适合记录较少的文件，是一种不稳定的排序方法。堆排序不适合记录较少的文件，是一种不稳定的排序方法。该算法的附加存储主要是在第二个该算法的附加存储主要是在第二个for循环中用来执行对象交循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为换时所用的一个临时对象。因此，该算法的空间复杂性为O(1)。v 算
39、法分析算法分析安安徽徽理理工工大大学学归并：归并：是将两个或两个以上的有序表合并成一个新的有序表。是将两个或两个以上的有序表合并成一个新的有序表。归并的基本操作是将两个位置相邻的有序记录子序列归并的基本操作是将两个位置相邻的有序记录子序列R i.m 和和R m+1.n 归并成一个有序记录序列归并成一个有序记录序列R i.n。2-路归并排序：路归并排序：基本思想：将两个有序子区间（有序表）合并成一个有序子区基本思想：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从长度
40、增加一倍，当区间长度从1增加到增加到n（元素个数）时，整个元素个数）时，整个区间变为一个，则该区间中的有序序列即为我们所需的排序结区间变为一个，则该区间中的有序序列即为我们所需的排序结果。果。9.5 归并排序归并排序安安徽徽理理工工大大学学例例如如，已已知知关关键键字字46，55，13，42，94，05，17，70，给给出出二二路归并排序过程。路归并排序过程。初初始始状状态态：46 55 13 42 94 05 17 70 一一趟趟归归并并：46 55 13 42 05 94 17 70 二二趟趟归归并并：13 42 46 55 05 17 94 70 三三趟趟归归并并：05 13 17 42
41、 46 55 70 94v 归并过程归并过程安安徽徽理理工工大大学学u 二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。而归并趟数为度的乘积。而归并趟数为 log2n ，每一趟归并的时间复杂度为每一趟归并的时间复杂度为O(n)。因此，二路归并排序的时间复杂度为因此，二路归并排序的时间复杂度为O(nlog2n)。u 利利用用二二路路归归并并排排序序时时，需需要要利利用用与与待待排排序序数数组组相相同同的的辅辅助助数数组组作作临临时时单单元元，故故该该排排序序方方法法的的空空间间复复杂杂度度为为O(n)，比比前前面面介介绍的其它排序
42、方法占用的空间大。绍的其它排序方法占用的空间大。u 二路归并排序是一种稳定的排序方法。二路归并排序是一种稳定的排序方法。v 算法分析算法分析安安徽徽理理工工大大学学9.6 各种排序方法的比较各种排序方法的比较排序方法排序方法比较次数比较次数移动次数移动次数稳定性稳定性附加存储附加存储最好最好最差最差最好最好最差最差最好最好最差最差直接插入直接插入nn20n21折半插入折半插入nlog2n0n21冒泡排序冒泡排序nn20n21快速排序快速排序nlog2nn2nlog2nn2log2nn2简单选择简单选择n20n1堆排序堆排序nlog2nnlog2n1归并排序归并排序nlog2nnlog2nn安安徽徽理理工工大大学学 P273 一、二、三、四（一、二、三、四（2，7）五（五（2，3）作业作业