《数据结构-王红梅-第8章 排序技术》由会员分享，可在线阅读，更多相关《数据结构-王红梅-第8章 排序技术（130页珍藏版）》请在金锄头文库上搜索。
1、数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社第第第第8 8 8 8章章章章 排序技术排序技术排序技术排序技术本章的基本内容是：本章的基本内容是：排序的基本概念排序的基本概念插入排序插入排序交换排序交换排序( (起泡、快速起泡、快速) )选择排序选择排序( (简单选择、堆简单选择、堆) )归并排序归并排序分配排序分配排序 各种排序算法的比较各种排序算法的比较数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社8.1 8.1 概概概概 述述述述 p 排排序序：给给定定一一组组记记录录的的集集合合r1, r2, , rn，其其相相应应的的关关键键码码分分别
2、别为为k1, k2, , kn，排排序序是是将将这这些些记记录录排排列列成成顺顺序序为为rs1, rs2, , rsn的的一一个个序序列列，使使得得相相应应的的关关键键码码满满足足ks1ks2ksn（称称为为升升序序）或或ks1ks2ksn（称为降序）。称为降序）。p 正序：正序：待排序序列中的记录已按关键码排好序。待排序序列中的记录已按关键码排好序。p 逆序（反序）：逆序（反序）：待排序序列中记录的排列顺序与排待排序序列中记录的排列顺序与排好序的顺序正好相反。好序的顺序正好相反。排序的基本概念排序的基本概念排序的基本概念排序的基本概念从操作角度看，排序是线性结构的一种操作从操作角度看，排序是
3、线性结构的一种操作 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社排序算法的稳定性：排序算法的稳定性：假定在待排序的记录集中，存在假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的多个具有相同键值的记录，若经过排序，这些记录的相对次序相对次序仍然保持不变，即在原序列中，仍然保持不变，即在原序列中，ki=kj且且ri在在rj之前，之前，而在排序后的序列中，而在排序后的序列中，ri仍在仍在rj之前，则称这种之前，则称这种排序算法是稳定的；否则称为不稳定的。排序算法是稳定的；否则称为不稳定的。 排序的基本概念排序的基本概念排序的基本概念排序的基本概念学
4、号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影85866872788.1 8.1 概概概概 述述述述 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社排序的基本概念排序的基本概念排序的基本概念排序的基本概念单键排序：单键排序：根据一个关键码进行的排序；根据一个关键码进行的排序；多键排序：多键排序：根据多个关键码进行的排序。根据多个关键码进行的排序。学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影8586687278按学号排序按学号
5、排序单键排序单键排序按成绩（高数英语思想品德）排序按成绩（高数英语思想品德）排序多键排序多键排序8.1 8.1 概概概概 述述述述 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社排序的基本概念排序的基本概念排序的基本概念排序的基本概念设关键码分别为设关键码分别为k1, k2, , km，多键排序有两种方法：，多键排序有两种方法： 依次对记录进行依次对记录进行m次排序，第一次按次排序，第一次按k1排序，第二排序，第二次按次按k2排序，依此类推。这种方法要求各趟排序所用排序，依此类推。这种方法要求各趟排序所用的算法是稳定的；的算法是稳定的； 将关键码将关键码k1, k2,
6、, km分别视为字符串依次首尾连分别视为字符串依次首尾连接在一起，形成一个新的字符串，然后，对记录序列接在一起，形成一个新的字符串，然后，对记录序列按新形成的字符串排序。按新形成的字符串排序。多键排序多键排序单键排序单键排序8.1 8.1 概概概概 述述述述 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社排序的分类排序的分类1. 内排序：内排序：在排序的整个过程中，待排序的所有记录在排序的整个过程中，待排序的所有记录全部被放置在内存中全部被放置在内存中2. 外排序外排序：由于待排序的记录个数太多，不能同时放由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录
7、放置在内存，另一部置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。间多次交换数据才能得到排序的结果。排序的基本概念排序的基本概念排序的基本概念排序的基本概念8.1 8.1 概概概概 述述述述 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社排序的分类排序的分类1. 基于比较：基于比较：基本操作基本操作关键码的比较和记录的移动，关键码的比较和记录的移动，其最差时间下限已经被证明为其最差时间下限已经被证明为（nlog2n）。 （1）插入排序）插入排序（2
8、）交换排序）交换排序（3）选择排序）选择排序（4）归并排序）归并排序2. 不基于比较不基于比较：根据关键码的分布特征。：根据关键码的分布特征。排序的基本概念排序的基本概念排序的基本概念排序的基本概念8.1 8.1 概概概概 述述述述 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社1. 基本操作基本操作。内排序在排序过程中的基本操作：。内排序在排序过程中的基本操作：比较比较：关键码之间的比较；：关键码之间的比较；移动移动：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。 2. 辅助存储空间辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存辅助存
9、储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。的其他存储空间。3. 算法本身的复杂程度算法本身的复杂程度。 排序算法的性能排序算法的性能排序算法的性能排序算法的性能8.1 8.1 概概概概 述述述述 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社排序算法的存储结构排序算法的存储结构排序算法的存储结构排序算法的存储结构从操作角度看，排序是线性结构的一种操作，待排序从操作角度看，排序是线性结构的一种操作，待排序记录可以用记录可以用顺序顺序存储结构或存储结构或链接链接存储结构
10、存储。存储结构存储。假定假定2：将待排序的记录序列排序为将待排序的记录序列排序为升序升序序列。序列。 int rn+1; /待排序记录存储在待排序记录存储在r1rn，r0留做他用留做他用假定假定1 1：采用采用顺序顺序存储结构，关键码为存储结构，关键码为整型整型，且记录，且记录只有关键码只有关键码一个一个数据项。数据项。8.1 8.1 概概概概 述述述述 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社8.2 8.2 插入排序插入排序插入排序插入排序插入排序的主要操作是插入排序的主要操作是插入插入，其基本思想是：，其基本思想是：每次将一个待排序的记录按其关键码的大小插每次
11、将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部入到一个已经排好序的有序序列中，直到全部记录排好序为止。记录排好序为止。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社基本思想基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。 直接插入排序直接插入排序直接插入排序直接插入排序有序序列有序序列无序序列无序序列r r1r r2r ri-1r rir rnr ri+1r r1r r2r ri-1r rir rnr ri+18.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据
12、结构（C+版）第版）第2版版清华大学出版社清华大学出版社基本思想基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。 （1）如何构造初始的有序序列？）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置）如何查找待插入记录的插入位置?直接插入排序直接插入排序直接插入排序直接插入排序需解决的关键问题需解决的关键问题?8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例 r 0 1
13、2 3 4 5 62121181825252222101025*25*212121212525i = 218182222101025*25*2525i = 318182222101025*25*22222525222221211010252521211515101025252525* *25252121151510102525* *2525212118181515101018181818101025*25*i = 41818i = 618182525* *i = 5r0的作用的作用?暂存单元暂存单元监视哨监视哨8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第
14、2版版清华大学出版社清华大学出版社解决方法：解决方法：将第将第1个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第2个记录起个记录起依次插入到这个有序表中，直到将第依次插入到这个有序表中，直到将第n个记录插入。个记录插入。关键问题关键问题(1)如何构造初始的有序序列？如何构造初始的有序序列？算法描述：算法描述：for (i=2; i=n; i+) 插入第插入第i个记录，即第个记录，即第i趟直接插入排序；趟直接插入排序；8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题(2)如何查找待插入记录的插入
15、位置如何查找待插入记录的插入位置?解决方法：解决方法：在在i- -1个记录的有序区个记录的有序区r1 ri- -1中插入记录中插入记录ri，首，首先顺序查找先顺序查找ri的正确插入位置，然后将的正确插入位置，然后将ri插入到相插入到相应位置。应位置。r0有两个作用：有两个作用：1. 进入循环之前暂存了进入循环之前暂存了ri的值，使得不致于因记录的值，使得不致于因记录的后移而丢失的后移而丢失ri的内容；的内容；2. 在查找插入位置的循环在查找插入位置的循环中充当中充当哨兵哨兵。算法描述：算法描述：r0=ri; j=i-1; while (r0rj) rj+1=rj; j-;8.2 8.2 插入排
16、序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri; j=i-1; while (r0=ri-1，内层循，内层循环会出现什么情况环会出现什么情况?8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析最好情况下（正序）：最好情况下（正序）： 1 12 23 34 45 5时间复杂度
17、为时间复杂度为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 58.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析最好最好情况下（正序）：情况下（正序）： 比较次数：比较次数：n-1移动次数：移动次数：2(n-1) 最坏最坏情况下（逆序或反序）：情况下（逆序或反序）： 时
18、间复杂度为时间复杂度为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比较次数：比较次数：移动次数：移动次数：2) 1)(2(2- -+ += = = =nnini2) 1)(4(1- -+ += =+ + nnin2= =i）（时间复杂度为时间复杂度为O(n)。8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社平均平均情况下（随机排列）：情况下（随机排列）： 直接插入排序算法性能分析直接插
19、入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：4) 1)(4(- -+ += = nnn2= =i4) 1)(2(2- -+ += = = =nnnii2（21+ +i）8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社空间性能：空间性能：需要一个记录的辅助空间。需要一个记录的辅助空间。直接插入排序算法是一种直接插入排序算法是一种稳定稳定的排序算法。的排序算法。直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析
20、直接插入排序算法性能分析直接插入排序算法简单、容易实现，适用于待排序直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。作使直接插入排序算法的效率降低。8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社如何改进直接插入排序如何改进直接插入排序?注意到，在插入第注意到，在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1 个个记录已经排好序，则在
21、寻找插入位置时，可以用折半记录已经排好序，则在寻找插入位置时，可以用折半查找来代替顺序查找，从而减少比较次数。查找来代替顺序查找，从而减少比较次数。请同学们写出这个改进的直接插入排序算法，并分析请同学们写出这个改进的直接插入排序算法，并分析时间性能。时间性能。8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社希尔排序希尔排序希尔排序希尔排序改进的着眼点：改进的着眼点：（1）若待排序记录按关键码）若待排序记录按关键码基本有序基本有序时，直接插入时，直接插入排序的效率可以大大提高；排序的效率可以大大提高；（2）由于直接插入排序算法
22、简单，则在待排序记录）由于直接插入排序算法简单，则在待排序记录数量数量n较小较小时效率也很高。时效率也很高。 8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社（1）应如何分割待排序记录，才能保证整个序列逐步）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？向基本有序发展？（2）子序列内如何进行直接插入排序？）子序列内如何进行直接插入排序？需解决的关键问题需解决的关键问题?基本思想：基本思想：将整个待排序记录将整个待排序记录分割分割成若干个子序列，成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的在子序列
23、内分别进行直接插入排序，待整个序列中的记录记录基本有序基本有序时，对全体记录进行直接插入排序。时，对全体记录进行直接插入排序。希尔排序希尔排序希尔排序希尔排序8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社基本有序基本有序：接近正序，例如：接近正序，例如1, 2, 8, 4, 5, 6, 7, 3, 9；局部有序局部有序：部分有序，例如：部分有序，例如6, 7, 8, 9, 1, 2, 3, 4, 5。局部有序不能提高直接插入排序算法的时间性能。局部有序不能提高直接插入排序算法的时间性能。 希尔排序希尔排序希尔排序希尔排序分
24、割待排序记录的目的分割待排序记录的目的?1. 减少待排序记录个数；减少待排序记录个数；2. 使整个序列向基本有序发展。使整个序列向基本有序发展。 子序列的构成不能是简单地子序列的构成不能是简单地“逐段分割逐段分割”，而是将相，而是将相距某个距某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。 启示启示?8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616
25、初始序列初始序列303008081313d = 4404021212525494925*25*161630300808131325252 21 125*25*303008084949131316164040d = 2131325252 21 1080825*25*16163030494940402525212125*25*303008081313161640404949d = 1080825252121131325*25*16163030404049490808252513131616212125*25*4040303049498.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构
26、（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：将相隔某个将相隔某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。增量应如何取？增量应如何取？希尔最早提出的方法是希尔最早提出的方法是d1=n/2，di+1=di/2。关键问题关键问题(1)(1)应如何分割待排序记录？应如何分割待排序记录？算法描述：算法描述：for (d=n/2; d=1; d=d/2) 以以d为增量，进行组内直接插入排序；为增量，进行组内直接插入排序；8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：在插入
27、记录在插入记录ri时，自时，自ri-d起往前跳跃式（跳跃幅起往前跳跃式（跳跃幅度为度为d）搜索待插入位置，并且搜索待插入位置，并且r0只是暂存单元，只是暂存单元，不是哨兵。当搜索位置不是哨兵。当搜索位置0，表示插入位置已找到。，表示插入位置已找到。在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃d个位置。个位置。在整个序列中，前在整个序列中，前d个记录分别是个记录分别是d个子序列中的第个子序列中的第一个记录，所以从第一个记录，所以从第d+1个记录开始进行插入。个记录开始进行插入。关键问题关键问题( (2) )子序列内如何进行直接插入排序？子序列内如何进行直接插入排序？8.2 8.2
28、 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始序列初始序列303008081313d = 4404021212525494925*25*161630300808131316164040ij1616j8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过
29、程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始序列初始序列303008081313d = 4404021212525494925*25*161630300808131325252 21 116164040ij2 21 1j8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始序列初始序列30
30、3008081313d = 4404021212525494925*25*161630300808131325252 21 116164040ij494908080808j8.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始序列初始序列303008081313d = 4404021212525494925*25*161630300808131325252 21
31、 116164040ij4949080825*25*303030308.2 8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始序列初始序列303008081313d = 4404021212525494925*25*161630300808131325252 21 116164040ij4949080825*25*30304040131316161313jj8.2
32、8.2 插入排序插入排序插入排序插入排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社算法描述：算法描述：for (i=d+1; i0 & r0rj+1） rjrj+1； exchange=j； 解决方法：解决方法：设变量设变量exchange记载记录交换的位置，则一趟排序后，记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。换的位置，且从此位置以后的所有记录均已经有序。8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）
33、第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：设设bound位置的记录是无序区的最后一个记录，则每位置的记录是无序区的最后一个记录，则每趟起泡排序的范围是趟起泡排序的范围是r1 rbound。在一趟排序后，从在一趟排序后，从exchange位置之后的记录一定是有位置之后的记录一定是有序的，所以序的，所以bound=exchange。关键问题关键问题：如何确定起泡排序的范围如何确定起泡排序的范围？050598981212696938385353818105059898696981811212交换交换3838交换交换5353交换交换8.3 8.3 交换排序交换排序交换排序交换排序数
34、据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：设设bound位置的记录是无序区的最后一个记录，则每位置的记录是无序区的最后一个记录，则每趟起泡排序的范围是趟起泡排序的范围是r1 rbound。在一趟排序后，从在一趟排序后，从exchange位置之后的记录一定是有位置之后的记录一定是有序的，所以序的，所以bound=exchange。关键问题关键问题：如何确定起泡排序的范围如何确定起泡排序的范围？算法描述：算法描述：bound=exchange; for (j=1; jrj+1） rjrj+1； exchange=j； 8.3 8.3 交换排序交换排序交
35、换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社0505989812126969383853538181解决方法：解决方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchange的初值为的初值为0，在在以后的排序过程中，只要有记录交换，以后的排序过程中，只要有记录交换，exchange的的值就会大于值就会大于0。这样，在一趟比较完毕，就可以通过。这样，在一趟比较完毕，就可以通过exchange的值是否为的值是否为0来判别是否有记录交换，从而来判别是否有记录交换，从而判别整个起泡排序的结束。判别整个起泡排序的结束。关键问题关键问题：如何判别起泡排序的
36、结束？如何判别起泡排序的结束？8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchange的初值为的初值为0，在在以后的排序过程中，只要有记录交换，以后的排序过程中，只要有记录交换，exchange的的值就会大于值就会大于0。这样，在一趟比较完毕，就可以通过。这样，在一趟比较完毕，就可以通过exchange的值是否为的值是否为0来判别是否有记录交换，从而来判别是否有记录交换，从而判别整个起泡排序的结束。判别整个起泡排序的结束。关键问题关键问题：如何判别起
37、泡排序的结束？如何判别起泡排序的结束？算法描述：算法描述：while ( (exchange) ) 执行一趟起泡排序；执行一趟起泡排序；8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社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 8.3 交换排序
38、交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 1 12 23 34 45 5时间复杂度为时间复杂度为O(n)。1 12 23 34 45 58.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社最坏情况（反序）：最坏情况（反序）：起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能
39、分析最好情况（正序）：最好情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 5 54 43 32 21 1时间复杂度为时间复杂度为O(n)；时间复杂度为时间复杂度为O(n2)。4 43 32 21 15 53 32 21 14 45 52 21 13 34 45 51 12 23 34 45 5比较次数：比较次数：移动次数：移动次数：2) 1(1- -= = = =nn(n-i)n-1i2) 1(1- -= = = =n3n3(n-i)n-1i平均情况：平均情况：时间复杂度为时间复杂度为O(n2)。8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）
40、第2版版清华大学出版社清华大学出版社快速排序快速排序快速排序快速排序改进的着眼点：改进的着眼点：在起泡排序中，记录的比较和移动是在起泡排序中，记录的比较和移动是在在相邻相邻单元中进行的，记录每次交换只能上移或下移单元中进行的，记录每次交换只能上移或下移一个一个单元，因而总的比较次数和移动次数较多。单元，因而总的比较次数和移动次数较多。减少总的比较次数和移动次数减少总的比较次数和移动次数增大记录的比较和移动距离增大记录的比较和移动距离较大记录从前面直接移动到后面较大记录从前面直接移动到后面较小记录从后面直接移动到前面较小记录从后面直接移动到前面8.3 8.3 交换排序交换排序交换排序交换排序数据
41、结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社快速排序的基本思想快速排序的基本思想快速排序的基本思想快速排序的基本思想首先选一个首先选一个轴值轴值（即比较的基准），通过一趟排序将（即比较的基准），通过一趟排序将待排序记录待排序记录分割分割成独立的两部分，前一部分记录的关成独立的两部分，前一部分记录的关键码均键码均小于或等于小于或等于轴值，后一部分记录的关键码均轴值，后一部分记录的关键码均大大于或等于于或等于轴值，然后分别对这两部分重复上述方法，轴值，然后分别对这两部分重复上述方法，直到整个序列有序。直到整个序列有序。如何选择轴值？如何选择轴值？如何实现分割（称一次划分）？如
42、何实现分割（称一次划分）？如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？如何判别快速排序的结束？如何判别快速排序的结束？需解决的关键问题需解决的关键问题?8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社选择轴值的方法：选择轴值的方法：1.使用第一个记录的关键码；使用第一个记录的关键码；2.选取序列中间记录的关键码；选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换记录的关键码，取关键码居中的作为轴值
43、并调换到第一个记录的位置；到第一个记录的位置；4.随机选取轴值。随机选取轴值。关键问题关键问题：如何选择轴值？如何选择轴值？选取不同轴值的后果：选取不同轴值的后果：决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社1313656527275050383849495555ji13133838656527275050494955551313656527275050494938385555关键问题关键问题：如何实现一次划分？如何实现一次划分？jj
44、iiijijjj8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：设待划分的序列是设待划分的序列是rs rt，设参数设参数i，j分别指向子分别指向子序列左、右两端的下标序列左、右两端的下标s和和t，令令rs为轴值，为轴值，（1）j从后从后向前向前扫描，直到扫描，直到rjri，将将rj移动到移动到ri的位置，使关键码小（同轴值相比）的记录移动到前的位置，使关键码小（同轴值相比）的记录移动到前面去；面去；（2）i从前从前向后向后扫描，直到扫描，直到rirj，将将ri移动到移动到rj的位置，使关键码大（同轴值比较
45、）的记录移动到后的位置，使关键码大（同轴值比较）的记录移动到后面去；面去；（3）重复上述过程，直到）重复上述过程，直到i=j。关键问题关键问题：如何实现一次划分？如何实现一次划分？8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：如何实现一次划分？如何实现一次划分？算法描述：算法描述：int Partition(int r , int first, int end) i=first; j=end; /初始化初始化 while (ij) while (ij & ri= rj) j-； /右侧扫描右侧扫描 if
46、(ij) rirj; i+; /将较小记录交换到前面将较小记录交换到前面 while (ij & ri= rj) i+； /左侧扫描左侧扫描 if (ij) rjri; j-; /将较大记录交换到后面将较大记录交换到后面 retutn i; /i为轴值记录的最终位置为轴值记录的最终位置8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。关键问题关键问题：如何处理分割得到的两个待排序子序列？：如何处理分割得到的两个待排序子序列？
47、 13132727383865655050494955551313272750503838494955556565ijij8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社算法描述：算法描述：关键问题关键问题：如何处理分割得到的两个待排序子序列？：如何处理分割得到的两个待排序子序列？ void QuickSort (int r , int first, int end ) pivotpos = Partition (r, first, end ); /一次划分一次划分 QuickSort (r, first, pivotpos
48、-1); /对前一个子序列进行快速排序对前一个子序列进行快速排序 QuickSort (r, pivotpos+1, end ); /对后一个子序列进行快速排序对后一个子序列进行快速排序8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：若待排序列中只有一个记录，显然已有序，否则进若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。行快速排序（即递归处理）。 关键问题关键问题：如何判别快速排序的结束？如何
49、判别快速排序的结束？ 8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社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 ); 算法描述：算法描述：关键问题关键问题：如何判别快速排序的
50、结束？如何判别快速排序的结束？ 8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社例：例：38, 27, 55, 50, 13, 49, 65的快速排序递归树如下：的快速排序递归树如下：38135055496527快速排序的递归执行过程可以用递归树描述。快速排序的递归执行过程可以用递归树描述。快速排序的时间性能分析快速排序的时间性能分析8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社快速排序的时间性能分析快速排序的时间性能分析快速排序的时间性能快速排序的时间
51、性能快速排序递归的深度快速排序递归的深度每次划分轴值的选取每次划分轴值的选取8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为右侧子表的长度相同，为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 8.3 交换排
52、序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社最坏情况：最坏情况：每次划分只得到一个比上一次划分少一个记录的子序每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为列（另一个子序列为空），为 O(n2)。最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为右侧子表的长度相同，为O(nlog2n)。快速排序的时间性能分析快速排序的时间性能分析平均情况：平均情况：为为O(nlog2n)。)() 1(21211nOnninni= =- -= =- -
53、 - -= =）（8.3 8.3 交换排序交换排序交换排序交换排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社选择排序的主要操作是选择排序的主要操作是选择选择，其主要思想是：，其主要思想是：每趟排序在当前待排序序列中选出关键码每趟排序在当前待排序序列中选出关键码最小最小的记录，添加到有序序列中。的记录，添加到有序序列中。 8.4 8.4 选择排序选择排序选择排序选择排序有序序列有序序列r r1r r2r ri-1r rir rnr rk无序序列无序序列r rnr ri+1r r1r r2r ri-1r rir ri交换交换最小记录最小记录数据结构（数据结构（C+版）第
54、版）第2版版清华大学出版社清华大学出版社简单选择排序简单选择排序简单选择排序简单选择排序基本思想：基本思想：第第i 趟在趟在n- -i+1（i=1,2, ,n- -1）个记录中选个记录中选取关键码最小的记录作为有序序列中的第取关键码最小的记录作为有序序列中的第i个记录。个记录。 需解决的关键问题需解决的关键问题?如何在待排序序列中选出关键码最小的记录？如何在待排序序列中选出关键码最小的记录？如何确定待排序序列中关键码最小的记录在有如何确定待排序序列中关键码最小的记录在有序序列中的位置？序序列中的位置？ 8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清
55、华大学出版社清华大学出版社简单选择排序示例简单选择排序示例08082121i i = 2= 2最小者最小者 08交换交换21,08最小者最小者 16交换交换25,16最小者最小者 21交换交换49,2121212828i i = 1= 125251616494908080808i i = 3= 32121080828284949212128284949161625251616161625258.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社i i = 4= 4最小者最小者 25交换交换25,28i i = 5= 5最小者最小者
56、 28不交换不交换简单选择排序示例简单选择排序示例494921210808282816162525252549492121080816162828252528284949212108081616282825252828无序区只有无序区只有一个记录一个记录8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：设置一个整型变量设置一个整型变量index，用于记录在一趟比较的过程用于记录在一趟比较的过程中关键码中关键码最小的记录位置。最小的记录位置。 关键问题关键问题：如何在无序区中选出关键码最小的记录？如何在无序区
57、中选出关键码最小的记录？212128282525161649490808indexindex index08088.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社算法描述：算法描述：index=i; for ( (j=i+1; j=n; j+) ) if ( (rjrindex) ) index=j;解决方法：解决方法：设置一个整型变量设置一个整型变量index，用于记录在一趟比较的过程用于记录在一趟比较的过程中关键码中关键码最小的记录位置。最小的记录位置。 关键问题关键问题：如何在无序区中选出关键码最小的记录？如何在无序区中
58、选出关键码最小的记录？8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：第第i趟简单选择排序的待排序区间是趟简单选择排序的待排序区间是ri rn，则则ri是无序是无序区第一个记录，所以，将区第一个记录，所以，将index所记载的关键码所记载的关键码最小的记录与最小的记录与ri交换交换。关键问题关键问题：如何确定：如何确定最小记录的最终位置？最小记录的最终位置？算法描述：算法描述： if ( (index!=i) ) ririndex; 8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+
59、版）第版）第2版版清华大学出版社清华大学出版社void selectSort ( int r , int n) for ( i=1; in; i+) index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j; if (index!=i) ri rindex; 简单选择排序算法简单选择排序算法8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次1 12 23 34 45 5
60、1 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 48.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社最坏情况：最坏情况：3(n-1)次次简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次空间性能：空间性能：需一个辅助空间。需一个辅助空间。稳定性：稳定性：是一种稳定的排序算法。是一种稳定的排序算法。4 45 52 23 31 1 1 15 52 23 34 41 12 25
61、 53 34 41 12 23 35 54 41 12 23 34 45 51 12 23 34 4比较次数：比较次数：)() 1(21211nOnninni= =- -= =- - - -= =）（简单选择排序的时间复杂度为简单选择排序的时间复杂度为O(n2)。8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社堆排序堆排序改进的着眼点：改进的着眼点：如何如何减少减少关键码间的关键码间的比较比较次数。若次数。若能利用每趟比较后的结果，也就是在找出键值最小能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记
62、录，则可减少后记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过面的选择中所用的比较次数，从而提高整个排序过程的效率。程的效率。减少关键码间的比较次数减少关键码间的比较次数查找最小值的同时，找出较小值查找最小值的同时，找出较小值8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社堆的定义堆的定义堆是具有下列性质的堆是具有下列性质的完全二叉树完全二叉树：每个结点的值都：每个结点的值都小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小根堆小根堆），），或每个结点的值都大于或等
63、于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值（称为（称为大根堆大根堆）。）。182032364525385040281. 小根堆的根结点是小根堆的根结点是所有结点的最小者。所有结点的最小者。2. 较小结点靠近根结较小结点靠近根结点，但不绝对。点，但不绝对。8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社堆的定义堆的定义堆是具有下列性质的堆是具有下列性质的完全二叉树完全二叉树：每个结点的值都：每个结点的值都小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小根堆小根堆），），或每个结点的值
64、都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值（称为（称为大根堆大根堆）。）。503845402836322018281. 大根堆的根结点是大根堆的根结点是所有结点的最大者。所有结点的最大者。2. 较大结点靠近根结较大结点靠近根结点，但不绝对。点，但不绝对。8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社堆和序列的关系堆和序列的关系将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。5038454028363220182850 38 45 32 36 40 28
65、 20 18 281 2 3 4 5 6 7 8 9 10采用顺序存储采用顺序存储8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社基本思想：基本思想：首先将待排序的记录序列构造成一个堆，首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。次小的记录，以此类推，直到堆中只有一个记录。 堆排序堆排序需解决的关键问题需解决
66、的关键问题?如何由一个无序序列建成一个堆（即初始建堆）？如何由一个无序序列建成一个堆（即初始建堆）？如何处理堆顶记录？如何处理堆顶记录？如何调整剩余记录，成为一个新堆（即重建堆）？如何调整剩余记录，成为一个新堆（即重建堆）？ 8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社堆调整堆调整堆调整：堆调整：在一棵完全二叉树中，根结点的左右子树均是在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？堆，如何调整根结点，使整个完全二叉树成为一个堆？2836321618253216182536288.
67、4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社void sift ( int r , int k, int m )/要筛选结点的编号为要筛选结点的编号为k，堆中最后一个结点的编号为堆中最后一个结点的编号为m i=k; j=2*i; while (j=m ) /筛选还没有进行到叶子筛选还没有进行到叶子 if (jm & rjrj) break; else ri rj; i=j; j=2*i; 堆调整堆调整算法描述：算法描述：8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清
68、华大学出版社关键问题关键问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？2825163218361632162825183625321628183625283236281618258.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社算法描述：算法描述：for (i=n/2; i=1; i-) sift(r, i, n) ; 关键问题关键问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？最后一个结点（叶子）的序号是最后一个结点（叶子）的序号是n，则最后一个分支，则最后一个分支结点即为结点结点即为结
69、点n的双亲，其序号是的双亲，其序号是n/2。8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：如何处理堆顶记录？如何处理堆顶记录？32362816182536 28 32 25 18 161 2 3 4 5 6对对应应交换交换16 28 32 25 18 361 2 3 4 5 6对对应应3216283618258.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社算法描述：算法描述：r1rn-i+1; 关键问题关键问题：如何处理堆顶记录？如何处
70、理堆顶记录？解决方法：解决方法：第第 i 次处理堆顶是将堆顶记录次处理堆顶是将堆顶记录r1与序列中第与序列中第n-i+1个个记录记录rn-i+1交换。交换。8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社321628361825关键问题关键问题：如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？163216323618258.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方法：解决方法：第第 i 次调整剩余记录，此时，剩余记录有次调整剩余记
71、录，此时，剩余记录有n-i个，调整个，调整根结点至第根结点至第n-i个记录。个记录。关键问题关键问题：如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？算法描述：算法描述：sift(r, 1, n-i);8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社堆排序算法堆排序算法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
72、, 1, n- -i); /重建堆重建堆 8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社堆排序算法的性能分析堆排序算法的性能分析第第1个个for循环是初始建堆，需要循环是初始建堆，需要O(n)时间；时间；第第2个个for循环是输出堆顶重建堆，共需要取循环是输出堆顶重建堆，共需要取n-1次堆顶次堆顶记录，第记录，第 i 次取堆顶记录重建堆需要次取堆顶记录重建堆需要O(log2i)时间，需时间，需要要O(nlog2n)时间；时间；因此整个时间复杂度为因此整个时间复杂度为O(nlog2n)，这是堆排序的这是堆排序的最好最好、最坏
73、最坏和和平均平均的时间代价。的时间代价。8.4 8.4 选择排序选择排序选择排序选择排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社归并排序归并排序归并排序的主要操作是归并排序的主要操作是归并归并，其主要思想是：，其主要思想是：将若干有序序列逐步归并，最终得到一个有序将若干有序序列逐步归并，最终得到一个有序序列。序列。 8.5 8.5 归并排序归并排序归并排序归并排序归并：归并：将两个或两个以上的有序序列合并成一个有序将两个或两个以上的有序序列合并成一个有序序列的过程。序列的过程。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社基本思想：基本思
74、想：将一个具有将一个具有n个待排序记录的序列看成个待排序记录的序列看成是是n个长度为个长度为1的有序序列，然后进行两两归并，得的有序序列，然后进行两两归并，得到到n/2个长度为个长度为2的有序序列，再进行两两归并，得的有序序列，再进行两两归并，得到到n/4个长度为个长度为4的有序序列，的有序序列，直至得到一个，直至得到一个长度为长度为n的有序序列为止。的有序序列为止。二路归并排序二路归并排序需解决的关键问题需解决的关键问题?如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？怎样完成一趟归并？怎样完成一趟归并？如何控制二路归并的结束？如何控制二路归并的结束？8.5 8.5
75、归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j608.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？602031544556520 605 3144 5565 60 20 31
76、 5 44 55 65ij5kj20i31j60归并可以就地进行吗归并可以就地进行吗?8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社在归并过程中，可能会破坏原在归并过程中，可能会破坏原来的有序序列，所以，将归并来的有序序列，所以，将归并的结果存入另外一个数组中。的结果存入另外一个数组中。 关键问题关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j608.5 8.5 归并排序
77、归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60子序列的长度一定相等吗子序列的长度一定相等吗?8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？602031544556520 605
78、 3144 5565 60 20 31 5 44 55 65ij5kj20i31j608.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？设相邻的有序序列为设相邻的有序序列为rs rm和和rm+1 rt，归并，归并成一个有序序列成一个有序序列r1s r1t s m m+1 t r s t r1 ijk8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社void Merge (
79、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+; /后一个子序列后一个子序列 关键问题关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？算法描述：算法描述：8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第
80、版）第2版版清华大学出版社清华大学出版社关键问题关键问题：怎样完成一趟归并？怎样完成一趟归并？602031544556520 605 3144 556560 20 31 5 44 55 65 5 20 31 60 44 55 65在一趟归并中，除最后一个有序序列外，其它有序在一趟归并中，除最后一个有序序列外，其它有序序列中记录的个数相同，用长度序列中记录的个数相同，用长度h表示。表示。8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：怎样完成一趟归并？怎样完成一趟归并？设参数设参数i指向待归并序列的第一个记录
81、，归并的步长是指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况：在归并过程中，有以下三种情况：若若in-2h+1，则相邻两个有序表的长度均为则相邻两个有序表的长度均为h，执行执行一次归并，完成后一次归并，完成后i加加2h，准备进行下一次归并；准备进行下一次归并；20 605 3144 5565ihi=1n-2h+1=4n-2h+18.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：怎样完成一趟归并？怎样完成一趟归并？设参数设参数i指向待归并序列的第一个记录，归并的步长是指向待归并序列的
82、第一个记录，归并的步长是2h，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：若若in-2h+1，则相邻两个有序表的长度均为则相邻两个有序表的长度均为h，执行执行一次归并，完成后一次归并，完成后i加加2h，准备进行下一次归并；准备进行下一次归并；算法描述：算法描述：while (in-2h+1) Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h;8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键问题关键问题：怎样完成一趟归并？怎样完成一趟归并？设参数设参数i指向待归并序列的第一
83、个记录，归并的步长是指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：若若in-h+1，则表示仍有两个相邻有序表，一个长则表示仍有两个相邻有序表，一个长度为度为h，另一个长度小于另一个长度小于h，则执行两个有序表的归并，则执行两个有序表的归并，完成后退出一趟归并。完成后退出一趟归并。20 605 3144 5565ihi=4n-2h+1=4n-h+1=6n-2h+1n-h+1=n-h+1) for (k=i; k=n; k+) r1k=rk; 8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华
84、大学出版社清华大学出版社void MergePass (int r , int r1 , int n, int h) i=1; while (in- -2h+1) /情况情况1 Merge (r, r1, i, i+h-1, i+2*h- -1); i+=2*h; if (in- -h+1) Merge (r, r1, i, i+h- -1, n); /情况情况2 else for (k=i; k=n; k+) /情况情况3 r1k=rk;一趟归并排序算法一趟归并排序算法8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社解决方
85、法：解决方法：开始时，有序序列的长度开始时，有序序列的长度h=1，结束时，有序序列的结束时，有序序列的长度长度h=n，用有序序列的长度来控制排序的结束。用有序序列的长度来控制排序的结束。关键问题关键问题：如何控制二路归并的结束？如何控制二路归并的结束？8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社算法描述：算法描述：void MergeSort (int r , int r1 , int n ) h=1; while (hn) MergePass (r, r1, n, h); h=2*h; MergePass (r1, r
86、, n, h); h=2*h; 关键问题关键问题：如何控制二路归并的结束？如何控制二路归并的结束？8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二路归并的递归实现二路归并的递归实现8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社void MergeSort2(int r , int r1 , int s, int t) if (s=t) r1s=rs; /递归出口递归出口 else m=(s+t)/2; Mergesort2(r, r1, s, m);
87、/归并排序前半个子序列归并排序前半个子序列 Mergesort2(r, r1, m+1, t); /归并排序后半个子序列归并排序后半个子序列 Merge(r1, r, s, m, t); 将两个已排序的子序列归并将两个已排序的子序列归并 二路归并的递归实现二路归并的递归实现8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二路归并排序算法的性能分析二路归并排序算法的性能分析二路归并排序算法的性能分析二路归并排序算法的性能分析时间性能：时间性能：一一趟趟归归并并操操作作是是将将r1rn中中相相邻邻的的长长度度为为h的的有有序序序
88、序列列进进行行两两两两归归并并，并并把把结结果果存存放放到到r11r1n中中，这这需需要要O(n)时时间间。整整个个归归并并排排序序需需要要进进行行 趟趟，因因此此，总总的的时时间间代代价价是是O(nlog2n)。这这是是归归并并排排序序算算法法的的最好最好、最坏最坏、平均平均的时间性能。的时间性能。空间性能：空间性能：算算法法在在执执行行时时，需需要要占占用用与与原原始始记记录录序序列列同同样样数数量量的的存储空间，因此空间复杂度为存储空间，因此空间复杂度为O(n)。 n2log8.5 8.5 归并排序归并排序归并排序归并排序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出
89、版社分配排序的基本思想分配排序的基本思想分配排序的基本思想分配排序的基本思想8.6 8.6 分配排序分配排序分配排序分配排序 分配排序是基于分配和收集的排序方法，其基本思想分配排序是基于分配和收集的排序方法，其基本思想是：先将待排序记录序列是：先将待排序记录序列分配分配到不同的桶里，然后再到不同的桶里，然后再把各桶中的记录依次把各桶中的记录依次收集收集到一起。到一起。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社桶式排序桶式排序桶式排序桶式排序 8.6 8.6 分配排序分配排序分配排序分配排序 桶式排序的基本思想是：假设待排序记录的值都在桶式排序的基本思想是：假设待排
90、序记录的值都在0m-1之之间，设置间，设置m个桶，首先将值为个桶，首先将值为i的记录分配到第的记录分配到第i个桶中，然后个桶中，然后再将各个桶中的记录依次收集起来。再将各个桶中的记录依次收集起来。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社桶式排序桶式排序桶式排序桶式排序 8.6 8.6 分配排序分配排序分配排序分配排序 需解决的关键问题需解决的关键问题?（1）如何表示桶？即如何存储具有相同键值的记录？）如何表示桶？即如何存储具有相同键值的记录？（2）如何进行分配操作？）如何进行分配操作？（3）如何进行收集操作？）如何进行收集操作？数据结构（数据结构（C+版）第版）
91、第2版版清华大学出版社清华大学出版社问题问题问题问题1 1如何表示桶？如何表示桶？如何表示桶？如何表示桶？8.6 8.6 分配排序分配排序分配排序分配排序 由于具有相同键值的记录可能会有多个，所以，应采用链接由于具有相同键值的记录可能会有多个，所以，应采用链接存储，为保证排序的稳定性，可以设存储，为保证排序的稳定性，可以设m个链队列作为桶的存个链队列作为桶的存储结构。为避免在分配和收集的过程中移动元素，采用静态储结构。为避免在分配和收集的过程中移动元素，采用静态链表作为链队列和待排序记录序列的存储结构，定义如下：链表作为链队列和待排序记录序列的存储结构，定义如下： struct Node /定
92、义静态链表存储待排序记录序列定义静态链表存储待排序记录序列 int key; /记录的键值记录的键值 int next; /游标，下一个键值在数组中的下标游标，下一个键值在数组中的下标 ;struct QueueNode /定义静态链队列存储桶定义静态链队列存储桶 int front; /队头指针，指向队头元素在数组中的下标队头指针，指向队头元素在数组中的下标 int rear; /队尾指针，指向队尾元素在数组中的下标队尾指针，指向队尾元素在数组中的下标 ;数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社问题问题问题问题1 1如何表示桶？如何表示桶？如何表示桶？如何表示桶
93、？8.6 8.6 分配排序分配排序分配排序分配排序 由于具有相同键值的记录可能会有多个，所以，应采用链接由于具有相同键值的记录可能会有多个，所以，应采用链接存储，为保证排序的稳定性，可以设存储，为保证排序的稳定性，可以设m个链队列作为桶的存个链队列作为桶的存储结构。为避免在分配和收集的过程中移动元素，采用静态储结构。为避免在分配和收集的过程中移动元素，采用静态链表作为链队列和待排序记录序列的存储结构。链表作为链队列和待排序记录序列的存储结构。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社问题问题问题问题22如何进行分配操作？如何进行分配操作？如何进行分配操作？如何进行
94、分配操作？8.6 8.6 分配排序分配排序分配排序分配排序 分配操作即是将记录插入到相应的队列中，入队在静态链表分配操作即是将记录插入到相应的队列中，入队在静态链表上实现，并修改相应队列的队头指针和队尾指针。上实现，并修改相应队列的队头指针和队尾指针。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社问题问题问题问题22如何进行分配操作？如何进行分配操作？如何进行分配操作？如何进行分配操作？8.6 8.6 分配排序分配排序分配排序分配排序 分配操作即是将记录插入到相应的队列中，入队在静态链表分配操作即是将记录插入到相应的队列中，入队在静态链表上实现，并修改相应队列的队头指
95、针和队尾指针。上实现，并修改相应队列的队头指针和队尾指针。 void Distribute(Node r , int n, QueueNode q , int m, int first) /first为静态链表的头指针，从下标为静态链表的头指针，从下标0开始存放待排序序列开始存放待排序序列 i = first; while (ri.next != -1) /依次分配每一个待排序记录依次分配每一个待排序记录 k = ri.key; if (qk.front = -1) qk.front = i; /处理队列为空的情况处理队列为空的情况 else rqk.rear.next = i; /在静态链表
96、中实现插在队列尾部在静态链表中实现插在队列尾部 qk.rear = i; /修改队尾指针修改队尾指针 i = ri.next; /i后移，处理下一个记录后移，处理下一个记录 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社问题问题问题问题33如何进行收集操作？如何进行收集操作？如何进行收集操作？如何进行收集操作？8.6 8.6 分配排序分配排序分配排序分配排序 收集操作即是将所有队列收尾相接。收集操作即是将所有队列收尾相接。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社问题问题问题问题33如何进行收集操作？如何进行收集操作？如何进行收集操作？如何
97、进行收集操作？8.6 8.6 分配排序分配排序分配排序分配排序 收集操作即是将所有队列收尾相接。收集操作即是将所有队列收尾相接。 void Collect(Node r , int n, QueueNode q , int m, int first) /first为静态链表的头指针从下标为静态链表的头指针从下标0开始存放待排序序列开始存放待排序序列 k = 0; while (qk.front != -1) /找到第一个非空队列找到第一个非空队列 k+; first = qk.front; /first为第一个记录，为第一个记录， last = qk.rear; /last为队列为队列k的最后
98、一个记录的最后一个记录 while (k m) /处理每一个静态链队列处理每一个静态链队列 k+; if (qk.front != -1) /第第k个队列非空个队列非空 rlast.next = qk.front; /将队列将队列k的队头和前一个队列的队尾相接的队头和前一个队列的队尾相接 last = qk.rear; /last为当前收集后最后一个记录为当前收集后最后一个记录 rlast.next = -1; /在静态链表中置尾标志在静态链表中置尾标志数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社桶式排序的复杂度分析桶式排序的复杂度分析桶式排序的复杂度分析桶式排序的复
99、杂度分析8.6 8.6 分配排序分配排序分配排序分配排序 p 桶式排序第一个循环初始化静态链表，时间性能为桶式排序第一个循环初始化静态链表，时间性能为O(n)，第二个循环初始化静态链队列，时间性能为第二个循环初始化静态链队列，时间性能为O(m)，进行分配，进行分配需要遍历静态链表，时间性能为需要遍历静态链表，时间性能为O(n)，进行收集需要遍历静，进行收集需要遍历静态链表和静态链队列，时间性能为态链表和静态链队列，时间性能为O( n + m)，因此，桶式排，因此，桶式排序的时间复杂度为序的时间复杂度为O(n + m)。p 桶式排序的空间复杂度是桶式排序的空间复杂度是O(m)，用来存储，用来存储
100、m个静态队列表个静态队列表示的桶。示的桶。p 由于桶采用队列作为存储结构，因此，桶式排序是稳定的。由于桶采用队列作为存储结构，因此，桶式排序是稳定的。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社基数排序基数排序基数排序基数排序8.6 8.6 分配排序分配排序分配排序分配排序 基数排序的基本思想基数排序的基本思想是：将关键码看成由若干个子关键码复是：将关键码看成由若干个子关键码复合而成，然后借助分配和收集操作。具体过程如下：合而成，然后借助分配和收集操作。具体过程如下：（1）第）第1趟排序按最次位关键码趟排序按最次位关键码kd-1将具有相同码值的记录将具有相同码值的记录
101、分配到一个队列中，然后再依次收集起来，得到一个按关键分配到一个队列中，然后再依次收集起来，得到一个按关键码码kd-1有序的序列；有序的序列；（2）一般情况下，第）一般情况下，第i趟排序按关键码趟排序按关键码kd-i将具有相同码值将具有相同码值的记录分配到一个队列中，然后再依次收集起来，得到一个的记录分配到一个队列中，然后再依次收集起来，得到一个按关键码按关键码kd-i有序的序列。有序的序列。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社基数排序基数排序基数排序基数排序8.6 8.6 分配排序分配排序分配排序分配排序 数据结构（数据结构（C+版）第版）第2版版清华大学出版
102、社清华大学出版社基数排序基数排序基数排序基数排序8.6 8.6 分配排序分配排序分配排序分配排序 p 假设待排序记录的关键码由假设待排序记录的关键码由d个子关键码复合而成，每个个子关键码复合而成，每个子关键码的取值范围为子关键码的取值范围为m个，则基数排序的时间复杂度为个，则基数排序的时间复杂度为O(d(n+m)，其中每一趟分配的时间复杂度是，其中每一趟分配的时间复杂度是O(n)，每一趟，每一趟收集的时间复杂度为收集的时间复杂度为O(n+m)，整个排序需要执行，整个排序需要执行d趟。趟。p 基数排序共需要基数排序共需要m个队列，因此空间复杂度为个队列，因此空间复杂度为O(m)。p 由于桶采用队
103、列作为存储结构，因此基数排序是稳定的。由于桶采用队列作为存储结构，因此基数排序是稳定的。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社8.7 各种排序方法的比较各种排序方法的比较对排序算法应该从以下几个方面综合考虑：对排序算法应该从以下几个方面综合考虑：时间复杂性；时间复杂性；空间复杂性；空间复杂性；稳定性；稳定性；算法简单性；算法简单性；待排序记录个数待排序记录个数n的大小；的大小；记录本身信息量的大小；记录本身信息量的大小；关键码的分布情况。关键码的分布情况。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社时间复杂度比较时间复杂度比较8.7 各
104、种排序方法的比较各种排序方法的比较排序方法排序方法平均情况平均情况最好情况最好情况最坏情况最坏情况直直 接接 插插 入入 排排 序序O( (n2) )O( (n) )O( (n2) )希希尔尔排排序序O( (nlog2n) )O( (n2) )O( (n1.3) )O( (n2) )起起泡泡排排序序O( (n2) )O (n)O( (n2) )快快速速排排序序O( (nlog2n) )O( (nlog2n) )O( (n2) )简简 单单 选选 择择 排排 序序O( (n2) )O( (n2) )O( (n2) )堆堆排排序序O( (nlog2n) )O( (nlog2n) )O (nlog2
105、n)归归并并排排序序O( (nlog2n) )O( (nlog2n) )O( (nlog2n) )基基数数排排序序O( (d(n +m)O( (d(n +m) O( (d(n +m)数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社空间复杂度比较空间复杂度比较8.7 各种排序方法的比较各种排序方法的比较排序方法排序方法辅助空间辅助空间直直 接接 插插 入入 排排 序序O( (1) )希希尔尔排排序序O( (1) )起起泡泡排排序序O( (1) )快快速速排排序序O( (log2n) ) O( (n) )简简 单单 选选 择择 排排 序序O( (1) )堆堆排排序序O( (1
106、) )归归并并排排序序O( (n) )基基数数排排序序O( (m) )数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社稳定性比较稳定性比较所有排序方法可分为两类，所有排序方法可分为两类，（1）一一类类是是稳稳定定的的，包包括括直直接接插插入入排排序序、起起泡泡排排序序和归并排序；和归并排序；（2）另另一一类类是是不不稳稳定定的的，包包括括希希尔尔排排序序、简简单单选选择择排序、快速排序和堆排序。排序、快速排序和堆排序。8.7 各种排序方法的比较各种排序方法的比较数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社算法简单性比较算法简单性比较从算法简单性看
107、，从算法简单性看，（1）一一类类是是简简单单算算法法，包包括括直直接接插插入入排排序序、简简单单选选择排序和起泡排序，择排序和起泡排序，（2）另另一一类类是是改改进进后后的的算算法法，包包括括希希尔尔排排序序、堆堆排排序、快速排序和归并排序，这些算法都很复杂。序、快速排序和归并排序，这些算法都很复杂。 8.7 各种排序方法的比较各种排序方法的比较数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社待排序的记录个数比较待排序的记录个数比较从从待待排排序序的的记记录录个个数数n的的大大小小看看，n越越小小，采采用用简简单单排排序序方方法法越越合合适适，n越越大大，采采用用改改进进
108、的的排排序序方方法法越越合合适适。因因为为n越越小小，O( (n2) )同同O( (nlog2n) )的的差差距距越越小小，并并且且输输入入和和调调试试简简单单算算法法比比输输入入和和调调试试改改进进算算法法要要少少用许多时间。用许多时间。 8.7 各种排序方法的比较各种排序方法的比较数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社记录本身信息量比较记录本身信息量比较记录本身信息量越大，移动记录所花费的时间就越多，记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。所以对记录的移动次数较多的算法不利。排序方法排序方法最好情况最好情况最坏情况
109、最坏情况平均情况平均情况直接插入排序直接插入排序O(n)O(n2)O(n2)起泡排序起泡排序0O(n2)O(n2)简单选择排序简单选择排序0O(n)O(n)8.7 各种排序方法的比较各种排序方法的比较数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社本章总结本章总结排序技术排序技术插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序直直接接插插入入排排序序希希尔尔排排序序起起泡泡排排序序快快速速排排序序简简单单选选择择排排序序堆堆排排序序二二路路归归并并排排序序 排序过程排序过程 算法设计过程算法设计过程 时间复杂度时间复杂度 空间复杂度空间复杂度改进改进分配排
110、序分配排序桶桶式式排排序序基基数数排排序序改进改进改进改进改进改进多多路路归归并并排排序序数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社关键码的分布情况比较关键码的分布情况比较当待排序记录按关键码有序时，插入排序和起泡排当待排序记录按关键码有序时，插入排序和起泡排序能达到序能达到O( (n) )的时间复杂度；对于快速排序而言，的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为这是最坏的情况，此时的时间性能蜕化为O( (n2) )；选；选择排序、堆排序和归并排序的时间性能不随记录序择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。列中关键字的分布而改变。8.7 各种排序方法的比较各种排序方法的比较
