数据结构(c语言版chap10.pptVIP

结束 第 * 页 第 十 章 排 序 第十章 排 序 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 struct{ KeyType key; //关键字项 InfoType otherinfo; //其它数据项 }RedType; //记录类型 typedef struct{ RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元 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