文档介绍：会计学
1
数据结构C语言CHAP
第 十 章 排 序
第十章 排 序
概述
插入排序
交换排序
选择排序
归并排序
第1页/共25页
概 述
学****要点
理解排序的定义和各种排序方法的特点；
了解各种方法的排序过程及其依据的原则；
理解“稳定”或“不稳定”的含义；
第2页/共25页
概 述
排序也是数据处理中经常使用的一种操作。例 高考考生信息管理系统提供了将考生按总分排序、按单科排序的功能；
1 排序定义
设R1 R2 R3 … Rn 是n个记录，k1,k2, k3 … kn为它们的关键字，排序就是将记录按关键字递增（或递减）的次序排列起来。
2 分类 按记录的存放位置分类有
内排序：待排记录放在内存 外排序：待排记录放在外存
·按排序原则分类（内排序） 插入排序 交换排序 选择排序
归并排序 基数排序
第3页/共25页
概 述
稳性排序：
在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。
例 设 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）申购价相同者按申购时间先后顺序成交
第4页/共25页
概 述
如何实现股票交易系统 ？ 申购队列：用线性表表示
交易前：将申购队列按申购价排序，显然为满足原则交易B），要求排序方法是稳定的
申购队列（09,10),(06,),(033,),(051,10))
排序后：((06,),(09,10),(051,10),(033,))
4 存贮方式 待排序的记录序列通常有下列三种存贮方法： 1）顺序表 2）静态链表：在排序过程，只需修改指针，不需要移动记录； 3）待排记录本身有放在连续单元中，同时另建一索引表——用于存放各记录存贮位置；排序时不移过记录本身，而移动索引表中的记录“地址”，在排序结束后再按地址调整记录的存贮位置
第5页/共25页
概 述
5 约定
在本章中
1)为简洁起见，对待排记录只写出其关键字序列
如对待排记录（(09,10),(06,),(033,),(051,10))
只写出其关键字序列（10，，，10）
2）将按关键字递增的顺序排序
第6页/共25页
概 述
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; //顺序表类型
第7页/共25页
概 述
6 本课程介绍如下几种排序方法
插入排序
交换排序
选择排序
归并排序
第8页/共25页
插入排序
基本思想
依次将待排记录插入到有序子表中，并使插入子表后仍保持有序，直到全部记录插入完毕；初始时，有序子表中只有一个元素。
直接插入排序 插入排序的关键：如何查找插入位置。直接插入排序（也称为顺序插入排序）是用顺序查找法定位插入位置。若采用二分查找法定位插入位置则得到另一种插入算法，二分插入排序
例：待排记录 49 38 65 97 76 13 27 49
（49）38 65 97