数据结构与算法 教学课件 作者 张晓蕾 第八章.ppt

《数据结构与算法 教学课件 作者 张晓蕾 第八章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第8章排序排序基本概念8.1三种基本的排序方法8.2高级排序方法8.3模板库STL的通用排序方法8.48.1排序基本概念排序（sorting）也称分类，是指把一系列杂乱无章的数据重新排列成有序的序列。排序方法分为两大类，即内部排序和外部排序。内部排序是指待排序的记录存放在计算机内存之中；外部排序是指待排序的记录数量很大，以致内存容纳不下而存放在外存储器中，排序过程需要访问外存。通常把排序所依据的数据项称为排序关键字，简称关键字。一般的记录类型可以定义为templateclassnodeX{public:Tkey;T1i

2、nfo;//<运算符的重载booloperator<(constnodeX&x){return(key

3、m的有序表中，使之仍保持有序，从而得到长度为m+1的新有序表。算法思路：设有一组排序关键字序列{key[0]，key[1]，……，key[n-1]}排序开始时认为仅包含key[0]的表是一个有序序列；然后把key[1]插入上述表长为1的表中，使之成为表长为2的有序序列；接着把key[2]插入表中，使之成为表长为3的有序序列；依此类推，最后把key[n-1]插入表长为n-1的有序表中，使之成为表长为n的有序序列。例8-1直接插入排序。设有一组关键字序列{81，76，60，22，98，33，12，79}这里n＝8，将其按由小到大的顺序排序，排序过程如图8

4、-1所示。算法8-1直接插入排序函数。算法及时间复杂度分析见教材p.189。初始状态第1趟第2趟第3趟第4趟第5趟第6趟第7趟81766022222212127681766060332222606081767660333322222281817660609898989898817676333333333398817912121212121298817979797979797998图8-1直接插入排序的过程冒泡（bubblesort）排序是最简单的交换排序方法。在排序过程中，关键字值较小的记录经过与其他记录的比较、交换，像水中的气泡一样向上冒出，自下而

5、上地移到序列的首部，故称此方法为冒泡排序法。8.2.2冒泡排序冒泡排序的算法思路：（1）令j取n-1至1，将r[j]与r[j-1]比较，如果r[j].key

6、[i-1]之中是剩余记录中关键字最小的记录。（4）最后一趟，令j取n-1至n-2，将r[n-1]与r[n-2]比较，把关键字较小的记录换到r[n-2]的位置上。经过n-1趟冒泡处理，r[n]中便是关键字最大的记录，至此排序完成。例8-2冒泡处理的示例。设有一组关键字序列{81，76，60，22，98，33，12，79}这里n＝8，将其按由小到大的顺序排序，冒泡排序过程如图8-2所示。初始状态第1趟第2趟第3趟第4趟第5趟761212121212817622222222608176333333226081766060982260817676339833

7、608179123398797981797979989898图8-2冒泡排序的过程算法8-2冒泡排序。算法及时间复杂度分析见教材p.190-191。简单选择排序（simpleselectionsort）算法思路：首先从关键字组{key[0]，key[1]，……，key[n-1]}中选择最小值，假如它是min0，则将min0与key[0]对换；然后从{key[1]，key[2]，……，key[n-1]}8.2.3选择排序中选择最小值，假如它是min1，则将min1与key[1]对换；如此重复进行选择和对换到第n-1趟，便完成了从小到大排序。例8-3选择

8、排序示例。设有一组关键字序列{81，76，60，22，98，33，12，79}这里n＝8，将其按由小到大的顺