5.2排序 基本概念 选择排序 三、插入排序 四、交换排序 五、归并排序 六、各种排序算法的比较 计算机软件技术基础 查找与排序
5.2 排序 一、基本概念 二、选择排序 三、插入排序 四、交换排序 五、归并排序 六、各种排序算法的比较 计算机软件技术基础 查找与排序
基本概念 1.排序 设有含n个记录的序列为{R1,R2…,Rn},其相应的关键字序列为 〔K1,K2……,Kn}。现要求确定一种排序p1,p2…pn,使其关键字满 足递增(或递减)的关系 Kp1≤K2≤…≤Kmn(或Kn1≥K2≥…≥Kpn) 使原序列成为一个按关键字有序的序列 计算机软件技术基础 查找与排序
一、基本概念 1. 排序 设有含n个记录的序列为{ R1,R2,…,Rn }，其相应的关键字序列为 { K1,K2,...,Kn }。现要求确定一种排序p1,p2,...pn, 使其关键字满 足递增（或递减）的关系： Kp1≤Kp2≤•••≤Kpn（或Kp1≥Kp2≥ •••≥Kpn） 使原序列成为一个按关键字有序的序列： { Rp1,Rp2,…Rpn } 计算机软件技术基础 查找与排序
基本概念 2.排序方法的稳定性 若K=K1(1≤i≤n,1≤j≤n,i≠j,在排序前R领先于R;,排序后 R仍领先于R,则称此排序方法是稳定的;反之称为不稳定的 3.排序的分类 若排序时待排序记录存放在内存中进行排序,则称为内部排序; 若待排序记录数量很大,在内存中一次不能容纳全部记录,需要在 非序过程中对外存进行访问,则称为外部排序 4.基本操作 1)对记录中关键字大小进行比较; 2)将记录从一个位置移到另一个位置。 计算机软件技术基础 查找与排序
一、基本概念 2.排序方法的稳定性 若Ki=Kj(1≤i≤n ,1≤j≤n ,i≠j)，在排序前Ri领先于Rj ，排序后 Ri仍领先于Rj ，则称此排序方法是稳定的；反之称为不稳定的。 3. 排序的分类 ▪ 若排序时待排序记录存放在内存中进行排序，则称为内部排序； ▪ 若待排序记录数量很大，在内存中一次不能容纳全部记录，需要在 排序过程中对外存进行访问，则称为外部排序。 4.基本操作 1）对记录中关键字大小进行比较； 2）将记录从一个位置移到另一个位置。 计算机软件技术基础 查找与排序
基本概念 5.排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销 可用算法执行中的数据比较次数与数据移动次数来衡量 算法运行时间代价的大略估算一般都按平均情况进行估算。对于那 些受对象排序码序列初始排列及对象个数影响较大的,需要按最好 情况和最坏情况进行估算 5.算法执行时所需的附加存储 评价算法好坏的另一标准 计算机软件技术基础 查找与排序
一、基本概念 5. 排序的时间开销: ◼ 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销 可用算法执行中的数据比较次数与数据移动次数来衡量。 ◼ 算法运行时间代价的大略估算一般都按平均情况进行估算。对于那 些受对象排序码序列初始排列及对象个数影响较大的，需要按最好 情况和最坏情况进行估算。 5. 算法执行时所需的附加存储 ◼ 评价算法好坏的另一标准。 计算机软件技术基础 查找与排序
基本概念 7.待排序的数据表 使用顺序存储结构存储 其数据类型定义如下 记录结点的类型定义 typedef struct I keywordtype key datatype data; F RECORDNODE 待排序的数据表是 RECORDNODE类型的数组 struct RECORDNODE a [MaxSize 计算机软件技术基础 查找与排序
一、基本概念 7. 待排序的数据表 ▪ 使用顺序存储结构存储 ▪ 其数据类型定义如下： ▪ 记录结点的类型定义： typedef struct{ keywordtype key; datatype data; }RECORDNODE; ▪ 待排序的数据表是RECORDNODE类型的数组 struct RECORDNODE a[MaxSize]; 计算机软件技术基础 查找与排序