数据结构(C语言版CHAP).ppt

第十章 排序,第 十 章 排 序,第十章 排 序 10.1 概述 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序,10.1 概 述,学习要点理解排序的定义和各种排序方法的特点；了解各种方法的排序过程及其依据的原则；理解“稳定”或“不稳定”的含义；,10.1 概 述,排序也是数据处理中经常使用的一种操作。例 高考考生信息管理系统提供了将考生按总分排序、按单科排序的功能；1 排序定义 设R1 R2 R3 Rn 是n个记录，k1,k2,k3 kn为它们的关键字，排序就是将记录按关键字递增（或递减）的次序排列起来。2 分类按记录的存放位置分类有 内排序：待排记录放在内存 外排序：待排记录放在外存按排序原则分类（内排序）插入排序 交换排序 选择排序 归并排序 基数排序,10.1 概 述,稳性排序：在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。例 设 49,38,65,97,76,13,27,49 是待排序列 排序后:13,27,38,49,49,65,76,97 稳定 排序后:13,27,38,49,49,65,76,97不稳定稳性排序的应用：例 股票交易系统 考虑一种股票交易(清华紫光)）1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾；2）股票交易系统按如下原则交易：A）申购价高者先成交 B）申购价相同者按申购时间先后顺序成交,10.1 概 述,如何实现股票交易系统？申购队列：用线性表表示交易前：将申购队列按申购价排序，显然为满足原则交易B），要求排序方法是稳定的申购队列（09,10),(06,10.5),(033,9.8),(051,10)排序后：(06,10.5),(09,10),(051,10),(033,9.8)4 存贮方式待排序的记录序列通常有下列三种存贮方法：1）顺序表2）静态链表：在排序过程，只需修改指针，不需要移动记录；3）待排记录本身有放在连续单元中，同时另建一索引表用于存放各记录存贮位置；排序时不移过记录本身，而移动索引表中的记录“地址”，在排序结束后再按地址调整记录的存贮位置,10.1 概 述,5 约定在本章中1)为简洁起见，对待排记录只写出其关键字序列 如对待排记录（(09,10),(06,10.5),(033,9.8),(051,10)只写出其关键字序列（10，10.5，9.8，10）2）将按关键字递增的顺序排序,10.1 概 述,3)待排序记录用顺序表存储顺序表类型说明#define MAXSIZE 20/一个用作示例的小顺序表的最大长度typedef int KeyType;/定义关键字类型为整数类型typedef structKeyType key;/关键字项InfoType otherinfo;/其它数据项RedType;/记录类型typedef structRedType rMAXSIZE+1;/r0闲置或用作哨兵单元Int length;/顺序表长度SqList;/顺序表类型,10.1 概 述,6 本课程介绍如下几种排序方法 插入排序 交换排序 选择排序 归并排序,10.2 插入排序,基本思想 依次将待排记录插入到有序子表中，并使插入子表后仍保持有序，直到全部记录插入完毕；初始时，有序子表中只有一个元素。直接插入排序插入排序的关键：如何查找插入位置。直接插入排序（也称为顺序插入排序）是用顺序查找法定位插入位置。若采用二分查找法定位插入位置则得到另一种插入算法，二分插入排序 例：待排记录 49 38 65 97 76 13 27 49（49）38 65 97 76 13 27 49（38 49）65 97 76 13 27 49（38 49 65）97 76 13 27 49（38 49 65 97）76 13 27 49（38 49 65 76 97）13 27 49（13 38 49 65 76 97）27 49（13 27 38 49 65 76 97）49（13 27 38 49 49 65 76 97）,一趟直接插入排序,10.2 插入排序,void InsertSort(SqList/插入到正确位置/InsertSort,初始时，有序子表中只有一个元素,10.2 插入排序,L.r0.key L.r4.key，L.r4记录后移,看一下外层For循环 i=5 时算法的执行的情况,L.r5复制为哨兵,L.r0.key L.r3.key找到插入位置,L.r5为待插入元素,插入！,10.2 插入排序,性能分析：基本操作 比较元素：比较、移动元素次数均取决于插入位置 移动元素处理第i个记录时 待排序列递增（正向）有序时，比较元素次数最少：1次 待排序列递减（逆向）有序时，比较元素次数最多：i 次 一般待排序列，平均比较元素次数：(i+1)/2 对n个记录待排序列,直接插入排序 待排序列正向有序时，比较元素次数最少：n-1次 待排序列逆向有序时，比较元素次数最多：(n+2)(n-1)/2次 一般待排序列，平均比较元素次数大约为：n2/4 类似可分析移动元素次数,10.2 插入排序,时间复杂度 待排序列正向有序时：0（n）待排序列逆向有序时：0（n2）一般待排序列：0（n2）特点：1)算法简单 2)时间复杂度为O（n2）3）初始序列基本（正向）有序时，时间复杂度为O（n）4）稳定排序 该方法适用于记录基本（正向）有序或n较少的情况,10.2 插入排序,四、希尔排序 直接插入排序法简单，适用于记录较少，或待排记录基本（正向）有序的情况。基于直接插入排序上是述特点，希尔提出了另一种插入排序算法。1 基本思想：1）将待排序记分为若干组，在各组内分别进行直接插入排序；2）作若干次使待排记录基本有序；3）对全部记录进行一次顺序插入排序；分组方法：选定一增量d，将间隔为d的记录作为一组例 待排记录 49 38 65 97 76 13 27 49 55 04 49 38 65 97 76 13 27 49 55 04 13 27 49 55 04 49 38 65 97 76 13 27 49 55 04 49 38 65 97 76 13 04 49 38 27 49 55 65 97 76 04 13 27 38 49 49 55 65 76 97,一趟希尔排序结果,两趟希尔排序结果,d=5,d=3,10.2 插入排序,特点 1）时间复杂度，取决于增量序列的选择，选择的好，效率优于直接插入排序，其时间复杂度为0（nlog2n）2）不稳定排序方法 3）适用于n 较大情况,10.3 交换排序,一、基本思想：将待排记录中两两记录关键字进行比较，若逆序而交换位置。例：49 38 65 97 76 13 27 49 若按关键字递增的顺序排序 则49 38 为逆序 不同的比较顺序就得到不同的交换排序方法二 起泡排序：顺序比较相邻的两记录的关键字，若逆序而交换位置三 快速排序1 基本思想1）选定一记录R，将所有其他记录关键字k与该记录关键字k比较,若 kk 则将记录换至R之后;2）继续对R前后两部分记录进行快速排序，直至排序范围为1;,10.3 交换排序,2 基本步骤 为简洁起见，对待排记录仍只写出其关键字序列1(一趟快速排序）设被指定的关键字为待排序列的第一个关键字k，i指向待排序列的的第一个关键字；j指向最后一个关键字；若i j 循环：1）从后向前将关键字与k比较，直至遇到小于k的关键字 k，k 前移；2）从前向后将关键字与k比较，直至遇到大于k的关键字k，k后移；（一趟快速排序后，“小”记录被移至k 前，“大”的记录被移至k 后2 继续对k前后两部分关键字进行快速排序，直至排序范围为1;,10.3 交换排序,被指定的关键字,从后向前，将关键字与49比较，直至遇到小于49的关键字，前移,从后向前，将关键字与49比较，直至遇到小于49的关键字，前移,从前向后，将关键字与49比较，直至遇到大于49的关键字，后移,从前向后，将关键字与49比较，直至遇到大于49的关键字，后移,从后向前，将关键字与49比较，直至遇到i=j,将49放至i处,49,一趟快速排序结束,10.3 交换排序,27 38 13 49 76 97 65 49 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97,两趟快速排序结束,三趟快速排序结束,快速排序结束,10.3 交换排序,例 待排记录 49 38 65 97 76 13 27 4927 38 13 49 76 97 65 49 27 38 13 49 76 97 65 49 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97,两趟快速排序结果,三趟快速排序结果,一趟快速排序结果,快速排序结束,特点：1)时间复杂度为0（nlog2n）2）不稳定,10.4 选择排序,10.4 选择排序,2 算法void SelectSort(SqList/与第个i记录交换/for/SelectSort3 特点：1)算法简单 2)时间复杂度为O（n2）3）稳定排序,10.5 归并排序,第十章 结束,