第10章挑秀 学司要点 理解和熟悉各种内部排序的基本思想和过程 掌握内部排序算法的时间复杂度的分析方法和结 论 要求能根据各种内部排序方法的优缺点及不同场 合选择合适的排序方法
学习要点 第10章 排序 ◼ 理解和熟悉各种内部排序的基本思想和过程 ◼ 掌握内部排序算法的时间复杂度的分析方法和结 论 ◼ 要求能根据各种内部排序方法的优缺点及不同场 合选择合适的排序方法
10.1基本概念 排序就是把一组记录（元素）按照某个域的值的递增（即由 小到大)或递减（即由大到小）的次序重新排列的过程。 一} 般情况下，假设含n个记录的序列为 (R1,R2,,Rn) 其相应关键字序列为 (K1,K2,,Kn) 需确定一种排列，使关键字满足如下的递增的关系 KK2.≤Kn 则按此关系将记录序列重新排列为(R,R2,,Rn)的操 作称之为排序
10.1 基本概念 排序就是把一组记录(元素)按照某个域的值的递增(即由 小到大)或递减(即由大到小)的次序重新排列的过程。 一般情况下，假设含n个记录的序列为 （R1 , R2 , …, Rn） 其相应关键字序列为 （K1 , K2 , …, Kn） 需确定一种排列，使关键字满足如下的递增的关系 Ki1 ≤Ki2 ≤…≤Kin 则按此关系将记录序列重新排列为(Ri1 , Ri2 , …, Rin)的操 作称之为排序
10.1基本概念 在排序的过程中也要引入关键字的概念。所谓关键字是 指在一个记录中可以标识该数据项的值，它是排序运算的 重要依据。关键字的选取应根据需要而定，比如在学生档 案表中，可选择“学号”为关键字来识别学生，也可选择 “年龄”为关键字对学生排序。 表10-1学生档案表 学号 姓名 年龄 性别 990001 王晓佳 18 男 990002 林一鹏 19 男 990003 谢宁 17 女 990004 张丽娟 18 女 990005 周涛 20 男 990006 李小燕 16 女
表10-1 学生档案表 学号 姓名 年龄 性别 990001 王晓佳 18 男 990002 林一鹏 19 男 990003 谢宁 17 女 990004 张丽娟 18 女 990005 周涛 20 男 990006 李小燕 16 女 在排序的过程中也要引入关键字的概念。所谓关键字是 指在一个记录中可以标识该数据项的值，它是排序运算的 重要依据。关键字的选取应根据需要而定，比如在学生档 案表中，可选择“学号”为关键字来识别学生，也可选择 “年龄”为关键字对学生排序。 10.1 基本概念
10.1基本概念 在上表中，若以每个记录的学号为关键字，可按排序码年龄 的递增（由小到大）排序，则所有记录的排序结果可简记为： {99006,16),(99003,17),(99001,18),(99004,18),(99002,19),(99005,20}; 也可能为： {99006,16),(99003,17),(99004,18),(99001,18),(99002,19),(99005,20}: 这两个结果都是按年龄的递增排序结果。 若按排序码姓名来进行递增排序，则得到的排序结果为： (99006,李小燕)，(99002，林一鹏)，(99001，王晓佳)，(99003，谢宁) (99004,张丽娟)，(99005，周涛)} 当然，我们还可以按排序码性别来进行递增排序， 在此不再 作进一步的分析
在上表中，若以每个记录的学号为关键字，可按排序码年龄 的递增(由小到大)排序，则所有记录的排序结果可简记为： {(99006,16),(99003,17),(99001,18),(99004,18),(99002,19),(99005,20)}； 也可能为： {(99006,16),(99003,17),(99004,18),(99001,18),(99002,19),(99005,20)}； 这两个结果都是按年龄的递增排序结果。 若按排序码姓名来进行递增排序，则得到的排序结果为： {(99006,李小燕),(99002,林一鹏),(99001,王晓佳),(99003,谢宁) (99004,张丽娟),(99005,周涛)} 当然，我们还可以按排序码性别来进行递增排序，在此不再 作进一步的分析。 10.1 基本概念
10.1基本概念 排序的分类 按照排序过程中使用内、外存的不同，将排序方法分 为内部排序和外部排序。 ”内部排序：如果待排序的记录放在计算机内存中进行排 序，整修排序过程不需要访问外存便能完成，则此类排 序称为一。 >内排序分类：插入排序、交换排序、选择排序、归并 排序和分配排序。 外部排序：如果待排序的记录数量比较大，排序期间文 件的全部记录不能同时存放在计算机的内存里，排序过 程中需要不断地进行内存和外存之间的数据交换，则此 类排序称为~
◼ 排序的分类 按照排序过程中使用内、外存的不同，将排序方法分 为内部排序和外部排序。 ❖ 内部排序：如果待排序的记录放在计算机内存中进行排 序，整修排序过程不需要访问外存便能完成，则此类排 序称为~ 。 ➢ 内排序分类：插入排序、交换排序、选择排序、归并 排序和分配排序。 ❖ 外部排序：如果待排序的记录数量比较大，排序期间文 件的全部记录不能同时存放在计算机的内存里，排序过 程中需要不断地进行内存和外存之间的数据交换，则此 类排序称为~ 。 10.1 基本概念
10.1基本概念 稳定性 在待排序的序列中，关键字可以是记录的主关键字， 也可以是记录的次关键字，或是若干数据项的组合。 由主关键字的定义可知，任何一个记录的无序序列经排 序后得到的结果是唯一的。 若是次关键字，排序的结果不唯一，因为等待排序的记 录序列中可能存在两个或两个以上关键字相等的记录 。 若采用的排序方法使具有相同关键字的记录在排序过程 中相对次序不变，则称此排序方法是稳定的，否则称为 不稳定的。 例如：假定一组记录为(15,67,23,15,40)，其中关键字同 为15的记录有两个
◼ 稳定性 在待排序的序列中，关键字可以是记录的主关键字， 也可以是记录的次关键字，或是若干数据项的组合。 ❖ 由主关键字的定义可知，任何一个记录的无序序列经排 序后得到的结果是唯一的。 ❖ 若是次关键字，排序的结果不唯一，因为等待排序的记 录序列中可能存在两个或两个以上关键字相等的记录。 若采用的排序方法使具有相同关键字的记录在排序过程 中相对次序不变，则称此排序方法是稳定的，否则称为 不稳定的。 ❖ 例如：假定一组记录为(15,67,23,15,40)，其中关键字同 为15的记录有两个。 10.1 基本概念
10.1基本概念 排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的 移动过程。因此排序的时间复杂性可以算法执行中的 数据比较次数及数据移动次数来衡量。 有序表与无序表 一组记录按排序关键字的递增或递减次序排列得到 的结果被称之为有序表，相应地，把排序前的状态称 为无序表。 正序表与逆序表 若有序表是按排序码升序排列的，则称为升序表或 正序表，否则称为降序表或逆序表。不失普遍性，我 们一般只讨论正序表
◼ 排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的 移动过程。因此排序的时间复杂性可以算法执行中的 数据比较次数及数据移动次数来衡量。 ◼ 有序表与无序表 一组记录按排序关键字的递增或递减次序排列得到 的结果被称之为有序表，相应地，把排序前的状态称 为无序表。 ◼ 正序表与逆序表 若有序表是按排序码升序排列的，则称为升序表或 正序表，否则称为降序表或逆序表。不失普遍性，我 们一般只讨论正序表。 10.1 基本概念
10.1基本概念 存储结构 在本章讨论的算法通常采用顺序存储结构，用一维 数组来实现，且记录按照关键字递增的顺序排列。 #define MAXSIZE 20 存储空间的最大值*/ typedef int KeyType; :定义关键字为整数类型*/ typedef struct{ KeyType key; 体关键字域* InfoType otherinfo;:/其它数据域/ RedType; 体记录类型*/ typedef struct RedType r[MAXSIZE+1];*R[O]用作监视哨单元*/ int length *顺序表长度*/ SqList;
#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 基本概念
10.2插入排序 10.2.1直接插入排序 基本思想 每次只考虑一个待排序的元素，用这个元素同已经 排序好的其他元素逐一进行比较，在找到适当的位置 后，将此记录插入，从而得到一个新的有序表，然后 再选择下一待排列的元素
10.2 插入排序 ◼ 基本思想 每次只考虑一个待排序的元素，用这个元素同已经 排序好的其他元素逐一进行比较，在找到适当的位置 后，将此记录插入，从而得到一个新的有序表，然后 再选择下一待排列的元素。 10.2.1 直接插入排序
10.2.1直接插入排序 基本步骤 初始状态：排序开始之前，整个数组被分为两个 部分：有序部分和无序部分。有序部分存放的是已 经排序好的记录；无序部分存放的是尚未排好的记 录。初始有序部分为r[1],无序部分为r[2]到r[n。 终止状态：有序部分存放的是整个数组，无序部分 为空。 基本操作：每次从无序部分取出一个记录（第一个） 将其同有序部分中的元素相比较，并按照关键字大 小将其插入到合适位置，使有序部分始终有序。直 至全部记录插入完毕
◼ 基本步骤 ◼ 初始状态：排序开始之前，整个数组被r分为两个 部分：有序部分和无序部分。有序部分存放的是已 经排序好的记录；无序部分存放的是尚未排好的记 录。初始有序部分为r[1]，无序部分为r[2]到r[n]。 ◼ 终止状态：有序部分存放的是整个数组，无序部分 为空。 ◼ 基本操作：每次从无序部分取出一个记录（第一个） 将其同有序部分中的元素相比较，并按照关键字大 小将其插入到合适位置，使有序部分始终有序。直 至全部记录插入完毕。 10.2.1 直接插入排序