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 直接插入排序