[工学]数据结构与算法C++语言版》第9章 内部排序.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 例9-9 扑克牌中每张牌都具有两个关键码：“花色”和“面值”，若规定扑克牌中“花色”的大小次序关系为：“梅花”“方片”“红桃”“黑桃”，“面值”的大小次序关系为：“2”“3”…“A”，且“花色”的地位高于“面值”，则扑克牌可按上述两种不同的排序方法整理成有序序列。 ① MSD：先按不同“花色”分成有次序的4堆，每一堆的牌均具有相同的“花色”，然后分别对每一堆按“面值”大小整理有序。 ② LSD：先按不同“面值”分成13堆，然后将这13堆牌自小至大叠在一起（“3”在“2”之上，“4”在“3”之上，……，最上面的是4张“A”），然后将这副牌整个颠倒过来再重新按不同“花色”分成4堆，最后将这4堆牌按自小至大的次序合在一起（这时，梅花在最下面，黑桃在最上面）。 基 数 排 序 链式基数排序 1. 算法思想 有的逻辑关键码可看成由若干个关键码复合而成，且每个关键码Kj都在相同的范围内，则按LSD进行排序时，只要从最低数位关键码开始，按关键码的不同值将序列中的记录“分配”到RADIX个队列中后再进行“收集”，如此重复d次，按这种方法实现的排序称为基数排序，其中，“基”指的是RADIX的取值范围。而链式基数排序就是用链表作存储结构的基数排序。例如，若关键码是数值，且其值都在0≤K≤999范围内，则可把每一个十进制数字看成一个关键码，即认为K由3个关键码（K0, K1, K2）组成，其中K0是百位数，K1是十位数，K2是个位数，对每一个关键码0≤Ki≤9（i=0, 1, 2），“基”为10。基数排序算法的实现参见以下例子的图。 例9-10 如图所示为链式基数排序三趟“分配”与“收集”的过程示例。 例9-10 例9-10 内排序方法的比较和讨论 1. 排序方法的比较 综合上面的讨论，下表中给出了本章所介绍的排序算法的性能比较情况。 内排序方法的比较和讨论 2. 影响排序效果的因素 不同的排序方法适应不同的应用环境和要求，因此在选择合适的排序方法时应综合考虑下列因素：待排序的记录数目n，记录的大小（规模），关键码的结构及其初始状态，对稳定性的要求，语言工具的条件，存储结构，时间和辅助空间复杂度等。经证明，借助于“比较”进行排序的算法在最坏情况下能达到的最好的时间复杂度为O(n log n)。 由此可知，本章讨论的所有排序方法中没有哪一种是绝对最优的，在实际应用中应根据不同情况进行选用，甚至可将多种方法结合起来使用。 本 章 总 结 学习要点 本章主要介绍了各种内部排序（插入排序、快速排序、选择排序、归并排序、基数排序）方法的特点和实现算法，以及各种排序方法在时间复杂度方面的讨论和比较，主要学习要点如下： ① 内排序方法的基本思想及稳定和非稳定排序的区别； ② 各种内排序算法及其优缺点； ③ 各种内部排序算法的时空性能和适用场合。 本 章 总 结 基本要求 （1）深刻理解排序的基本概念和各种排序方法的算法思想及特点 ① 清楚排序的定义，稳定与不稳定排序、内排序与外排序的概念及区别； ② 知道各种排序的实质是以关键码的比较为基础的； ③ 知道各种内部排序（插入、快速、选择、归并、基数等排序）方法的主要优缺点及适用场合。 （2）掌握插入排序、快速排序和选择排序的基本思想和算法 ① 掌握快速排序的基本思想，一趟快速排序交换过程及每趟快速排序的结果； ② 掌握直接插入排序算法的基本思想及时空性能指标； ③ 知道快速排序算法的时空性能及交换排序的指导思想； 本 章 总 结 ④ 知道直接选择排序的基本思想及其性质； ⑤ 掌握堆排序及归并排序和外部排序的基本思想和实现算法； ⑥ 掌握堆排序的表示方法、调整方法和“筛选”过程； ⑦ 掌握建堆方法、堆排序算法的时空性能； ⑧ 掌握归并排序的指导思想和将两个有序文件合并成一个有序文件的算法； ⑨ 知道2路归并排序的基本思想和时空性能。 重点与难点 本章的重点是：快速排序和直接插入排序及堆排序的实现算法。难点是：二叉排序树和堆排序算法及时空性能分析。 * * * * * * * * * * * * * * * * * * * * * * 交 换 排 序 一趟快速排序算法： 例9-6 以关键码序列{21, 25, 49, 25*, 16, 08}为例，一趟快速排序的过程如（a）所示，整个序列的快速排序过程如（b）所示。 从本例可看出，快速排序方法是一个不稳定的排序方法。快速排序通常被认为是具有相同数量级 的排序方法中平均性能最好的方法，但是，如果初始序列中关键码是有序或基本有序的，则快速排序