第十章排序 基本概念 插入排序 快速排序 选择排序 归并排序 ·基教排序 10.1概念 >排序 构 设含有n个记录的文件{R1R2,Rn}, 之其相应的关键字为{K,K2Kn},需确定 1,2,…,n的一种排列p1,p2,…,pn,使其相应 部的关键字满足如下的非递减(或非递增)关 系Kn=K2=.,<=Km,从而使序列 {Rp,Rp2…,Rmn}按关键字有序,该过程称为 排序
1 第十章 排序 • 基本概念 • 插入排序 • 快速排序 • 选择排序 • 归并排序 • 基数排序 数 据 结 构 之 内 部 排 序 2 10. 1 概念 ¾排序 设含有n个记录的文件{R1,R2,...,Rn}， 其相应的关键字为{K1,K2,...,Kn}，需确定 1,2, …, n的一种排列p1,p2, …, pn,使其相应 的关键字满足如下的非递减(或非递增)关 系 Kp1<=Kp2<=…<=Kpn, 从而使序列 {Rp1,Rp2,...,Rpn}按关键字有序, 该过程称为 排序
据结构 排序的稳定性 对所有的K=K(i≠j,若排序前R领先于 排序后R仍领先于R,则称该排序方法是稳 定的反之,若可能使排序后的序列中R领先 于R1,则称所用的排序方法为不稳定的 部 稳定性是对序列中的两个相同关键字的 记录在初始序列和最终有序序列中相对位置( 即领先关系)是否变化的描述。 据>内部排序和外部排序 构 内部排序:待排序文件的全部记录存放在 内存进行的排序,称为内部排序。 外部排序:待排序记录的数量很大,以致 内存一次不能容纳全部记录,排序过程中 内部排序 需要进行内外存数据交换的排序,称为外 部排序
2 数 据 结 构 之 内 部 排 序 3 ¾ 排序的稳定性 对所有的Ki=Kj (i≠j), 若排序前Ri领先于 Rj, 排序后Ri仍领先于Rj, 则称该排序方法是稳 定的；反之，若可能使排序后的序列中Rj领先 于Ri, 则称所用的排序方法为不稳定 的。 稳定性是对序列中的两个相同关键字的 记录在初始序列和最终有序序列中相对位置( 即领先关系)是否变化的描述。 数 据 结 构 之 内 部 排 序 4 ¾ 内部排序和外部排序 ¾ 内部排序：待排序文件的全部记录存放在 内存进行的排序，称为内部排序。 ¾ 外部排序：待排序记录的数量很大, 以致 内存一次不能容纳全部记录, 排序过程中 需要进行内外存数据交换的排序，称为外 部排序
据结构 内排序分类 按排序过程依据的原则分为:插入排序 交换排序 选择排序 归并排序 部 计数排序 按排序过程所需的工作量分:简单排序O(mn2) 先进排序O( nlog n) 基数排序O(d.n) 存储形式 数据结构 连续存放在地址连续的一组存储单元上 静态链表存储形式。 待排记录存放在一组地址连续的存储单 元中,同时另设一个指示各个记录存储位置 内部排序 的地址向量,在排序过程中不移动记录本身, 只修改这些记录的地址,在排序结束之后在 按照地址向量中的值调整记录的存储位置
3 数 据 结 构 之 内 部 排 序 5 ¾ 内排序分类 按排序过程依据的原则分为：插入排序 交换排序 选择排序 归并排序 计数排序 按排序过程所需的工作量分：简单排序 O(n2) 先进排序 O(nlog n) 基数排序 O(d．n) 数 据 结 构 之 内 部 排 序 6 ¾ 存储形式 ¾ 连续存放在地址连续的一组存储单元上。 ¾ 静态链表存储形式。 待排记录存放在一组地址连续的存储单 元中，同时另设一个指示 各个记录存储位置 的地址向量，在排序过程中不移动记录本身， 只修改这些记录的地址，在排序结束之后在 按照地址向量中的值调整记录的存储位置
数>排序算法的性能度量 结 排序算法的时间复杂度: 记录移动次数、比较次数; 空间复杂度; >排序方法的稳定性 内部排序 #define maXsize 100 ∥顺序表的长度 据 Typedef int Key Type; ∥关键字类型为整数 类型 构 ypedef struct{ Key Type key;/关键字项 InfoType otherinfo; )其它数据项 A JRedType ∥记录类型 s type struct( RedType r[MAXSIZE+1; 排 r10空作为哨兵 int length; ∥顺序表长度 JSlIst ∥顺序表类型
4 数 据 结 构 之 内 部 排 序 7 ¾ 排序算法的性能度量 ¾ 排序算法的时间复杂度： 记录移动次数、比较次数； ¾ 空间复杂度； ¾ 排序方法的稳定性 数 据 结 构 之 内 部 排 序 8 #define MAXSIZE 100 //顺序表的长度 Typedef int KeyType; //关键字类型为整数 类型 Typedef struct{ KeyType key; //关键字项 InfoType otherinfo; //其它数据项 }RedType; //记录类型 type struct { RedType r[MAXSIZE+1]; //r[0]空作为哨兵 int length; //顺序表长度 }SqList; //顺序表类型
10.2插入排序 >直接插入排序 基本操作:是将一个记录插入到已排 好序的有序表中,从而得到一个新的 记录数增1的有序表。 整个排序过程:先将原序列中的第 部 个记录看成是一个有序的子序列,然 序 后,从第2个记录起逐个进行插入,直 至整个序列变成按关键字非递减有序 序列为止 例:已知关键字为{49386597761327 数49},采用直接插入排序方法对其进行排序 据 结初始关键字:(49)38659776132749 构 i=2:(38)(3849)659776132749 65)9776132749 i=4:(97)638496597)76132749 排 i=5:(76)(38 657697)132749 序 i=6:(13)(133849657697)2749 (27)(13273849657697)49 i=8:(49)(1327384949657697)
5 数 据 结 构 之 内 部 排 序 9 10. 2 插入排序 ¾ 直接插入排序： ¾ 基本操作：是将一个记录插入到已排 好序的有序表中，从而得到一个新的 记录数增1的有序表。 ¾ 整个排序过程：先将原序列中的第一 个记录看成是一个有序的子序列，然 后，从第2个记录起逐个进行插入，直 至整个序列变成按关键字非递减有序 序列为止。 数 据 结 构 之 内 部 排 序 10 例：已知关键字为{ 49 38 65 97 76 13 27 49}，采用直接插入排序方法对其进行排序。 初始关键字： （49） 38 65 97 76 13 27 49 i=2: (38) (38 49) 65 97 76 13 27 49 i=3: (65) (38 49 65) 97 76 13 27 49 i=4: (97) (38 49 65 97) 76 13 27 49 i=5: (76) (38 49 65 76 97) 13 27 49 i=6: (13) (13 38 49 65 76 97) 27 49 i=7: (27) (13 27 38 49 65 76 97) 49 i=8: (49) (13 27 38 49 49 65 76 97)