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

《数据结构(C语言版CHAP.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第十章排序第十章排序第十章排序10.1概述10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.1概述学习要点理解排序的定义和各种排序方法的特点；了解各种方法的排序过程及其依据的原则；理解“稳定”或“不稳定”的含义；10.1概述排序也是数据处理中经常使用的一种操作。例高考考生信息管理系统提供了将考生按总分排序、按单科排序的功能；1排序定义设R1R2R3…Rn是n个记录，k1,k2,k3…kn为它们的关键字，排序就是将记录按关键字递增（或递减）的次序排列起来。2分类按记录的存放位置分类有内排序：待排记录放在内存外排序：待排记录放在外存·按排序原则分类（内

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）申

3、购价高者先成交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）待排记录本身有放在连续单元中，同时另建一索引表——用于存放各记录存贮位置；排序时不移过记录本身，而

4、移动索引表中的记录“地址”，在排序结束后再按地址调整记录的存贮位置10.1概述5约定在本章中1)为简洁起见，对待排记录只写出其关键字序列如对待排记录（(09,10),(06,10.5),(033,9.8),(051,10))只写出其关键字序列（10，10.5，9.8，10）2）将按关键字递增的顺序排序10.1概述3)待排序记录用顺序表存储顺序表类型说明#defineMAXSIZE20//一个用作示例的小顺序表的最大长度typedefintKeyType;//定义关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotheri

5、nfo;//其它数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元Intlength;//顺序表长度}SqList;//顺序表类型10.1概述6本课程介绍如下几种排序方法插入排序交换排序选择排序归并排序10.2插入排序基本思想依次将待排记录插入到有序子表中，并使插入子表后仍保持有序，直到全部记录插入完毕；初始时，有序子表中只有一个元素。直接插入排序插入排序的关键：如何查找插入位置。直接插入排序（也称为顺序插入排序）是用顺序查找法定位插入位置。若采用二分查找法定位插入位置则得到另一种插入算

6、法，二分插入排序例：待排记录4938659776132749（49）38659776132749（3849）659776132749（384965）9776132749（38496597）76132749（3849657697）132749（133849657697）2749（13273849657697）49（1327384949657697）一趟直接插入排序10.2插入排序voidInsertSort(SqList&L){//对顺序表L作直接插入排序。For(i=2;i<=L.length;++i){ifLT(L.r[i].key,L.r[i-1].key){//若

7、L.r[i].key