数据结构(严蔚敏)第10章

22.05.2020，第页，第10章排序，22.05.2020，在第一章中，以选择排序和起泡的顺序为例，讨论了算法的实践复杂性。你还记得吗？22.05.2020，第页，学习目标，1。了解排序的定义以及各种排序方法的特性，并灵活应用。排序方法分为五类：插入排序、交换排序、选择排序、合并排序和计数排序，这三类基于“关键字之间的比较”排序的方法有所不同。掌握各种排序方法时间复杂度的分析方法。在“关键字之间的比较次数”中，可以分析排序算法的平均和最坏的时间性能。根据平均时间复杂性，内部排序可以分为三类：O(n2)的简单排序方法、O(nlogn)的有效排序方法和O(dn)的标准排序方法。3.要理解排序方法“稳定”或“不稳定”的含义，理解在哪些情况下应用的排序方法必须稳定。22.05.2020，页面、【重点和难点】、【希尔对齐】、【快速对齐】、【堆对齐和合并】等有效方法是本章的学习重点和难点。知识点、排序、直接插入排序、半插入排序、表插入排序、定位台阶对齐、气泡排序、快速排序、简单选择排序、堆排序、双路径排序、基准排序、排序方法的综合比较。22.05.2020，页面、学习指南、本章的主要目的是理解实施各种排序方法时的原理和主要任务(“关键字间比较”和“记录移动”)的时间分析。在学习中，要把握各种排序方法实施的要点，在基础知识问题中通过对算法的手动执行和比较分析，有效地把握各种排序过程的排序特性，注意相同的排序方法可以在不同的教科书中采用不同的写作形式描述的算法。在学习本章的过程中需要练习的算法设计为10.23、10.25、10.27、10.32、10.34、10.38，10.42和10.45。22.05.2020，第页，10.1概览，10.2插入排序，10.3快速排序，10.4堆排序，10.5合并排序，10.6基准排序，10.7各种排序方法的集成比较，10.8外部排序，22.05.2020，第页，10.1概述，1，对齐的定义，2，内部对齐和外部对齐，3，内部对齐方法的分类，22.05.2020，第页，1，排序是什么？排序是计算机经常执行的操作，用于将一组“未排序”的记录序列调整为“已排序”的记录序列。例如，以下关键字序列：52，49，80，36，14，58，61，23，97，75，14，23，36，49，52，58，61，75，80，97，22页面，通常包含n条记录的序列为R1，R2，Rn其关键字序列为k1，k2，Kn，则这些关键字可以相互比较。也就是说，kp1 kp2 kpn将父记录序列设置为rp1，rp2，Rpn重新排序的操作称为排序。22.05.2020，第页、第2页、内部对齐和外部对齐在整个排序过程完成而无需访问外部存储时，这种对齐问题称为内部对齐。相反，如果参与排序的记录数很多，并且整个序列的排序过程在内存中未完成，则此类排序问题称为外部排序。22.05.2020，页面、三、内部排序方式、内部排序过程是逐步扩展记录的排序顺序长度的过程。、排序、排序顺序区域、已排序序列区域、未排序序列区域、已排序序列区域、22.05.2020、页面，根据不同的“扩展有序序列长度”方法，内部排序方法通常包括插入类、交换类、选择类、合并类、其他方法、22.05.2020、页，记录的数据类型为：# definedsize 1000/有序表的最大长度，typedefintKeyType，/关键字类型为整数类型，typedefstruct KeyTypekey/关键字项目InfoTypeotherinfo/其他数据项 RcdType/记录类型，typedef struct rcd typermaxsize 1；/r0空闲intlength/连续表格长度 SqList/顺序表格类型，22.05.2020，第页，1 .插入类并将一个或多个记录“插入”到未排序的子序列中，以增加记录的已排序子序列的长度。22.05.2020，第页，第2页。“交换”未排序序列的记录，以获取关键字最小或最大的记录，然后将其添加到已排序的子序列，以增加记录的已排序子序列的长度。22.05.2020，第页，3 .选择类以“选择”记录的未排序子序列中关键字最小或最大的记录，然后将其添加到已排序子序列以增加记录的已排序子序列的长度。22.05.2020，第页，4 .合并类，“合并”两个或多个记录排序子序列，以逐渐增加记录排序序列的长度。5 .其他方法，22.05.2020，页面，10.2插入排序，22.05.2020，页面，顺序序列R1.i-1、Ri、无顺序序列Ri.n，顺序序列R1.i，无顺序序列Ri 1.n、22.05.2020、页面