数据结构(严蔚敏)课件第10章.ppt

《数据结构(严蔚敏)课件第10章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十章排序7/21/2021第页【课前思考】1.你熟悉排序吗？你过去曾经学过哪些排序方法？在第一章中曾以选择排序和起泡排序为例讨论算法实践复杂度，不知你还记得吗？2.你自己有没有编过排序的程序？是用的什么策略？7/21/2021第页【学习目标】1．理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方法，基于"关键字间的比较"进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。　　2．掌握各种排序方法的时间复杂度的分析方法。能从"关键字间的比较次数"分析排序算法的平均情况和最坏情况的时间性能。按

2、平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(n·logn)的高效排序方法和O(d·n)的基数排序方法。　　3．理解排序方法"稳定"或"不稳定"的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。7/21/2021第页【重点和难点】希尔排序、快速排序、堆排序和归并排序等高效方法是本章的学习重点和难点。【知识点】排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。7/21/2021第页【学习指南】本章学习的要点主要是了解各种排序方法实现时所依据的原则

3、以及它们的主要操作（“关键字间的比较”和“记录的移动”）的时间分析。学习中应注意掌握各种排序方法实现的要点，可通过对基础知识题中算法的手工执行和比较分析，切实掌握各种排序过程的排序特点所在，注意同一排序方法在不同的教科书上可以有不同书写形式描述的算法。在学习本章过程中需练习的算法设计题为：10.23，10.25，10.27，10.32，10.34，10.38,10.42和10.45。7/21/2021第页10.1概述10.2插入排序10.3快速排序10.4堆排序10.5归并排序10.6基数排序10.7各种排序方法的综合比较10.8外部排序7/21/2021第页10.1概

4、述一、排序的定义二、内部排序和外部排序三、内部排序方法的分类7/21/2021第页一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,977/21/2021第页一般情况下，假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重

5、新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。7/21/2021第页二、内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。7/21/2021第页三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区7/21/2021第页基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法7/21/2021第页待排记录的数据类型定

6、义如下:#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表长度}SqList;//顺序表类型7/21/2021第页1.插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。7/21/2021第页2.交换类通过“交换”

7、无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。7/21/2021第页3.选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。7/21/2021第页4.归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。5.其它方法7/21/2021第页10.2插入排序7/21/2021第页有序序列R[1..i-1]R[i]无序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]无