第3章排序 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第3章排序 胡建华 2021/2/19 计算机教研室 第 1 页 第 3 章 排序
◎31排序的基本概念 排序是计算机内经常进行的一种操作,其目的 是将一组“无序”的记录序列调整为“有序” 的记录序列。 例如:将下列关键字序列 52,49,80,36,14,58,61,23,97,75 调整为 14,23,36,49,52,58,61,75,80,97 计算机教研宦 第2页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第2页 3.1 排序的基本概念 • 排序是计算机内经常进行的一种操作，其目的 是将一组“无序”的记录序列调整为“有序” 的记录序列。 例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97
◎31排序的基本概念 般情况下,假设含n个记录的序列为 R31,R2 其相应的关键字序列为 e K1,K2 K n 这些关键字相互之间可以进行比较,即在它们之间 存在着这样一个关系: Kn1≤K≤≤K p pn 按此固有关系将上式记录序列重新排列为 1,1p2 p 的操作称作排序。 计算机教研宦 第3页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第3页 3.1 排序的基本概念 一般情况下，假设含n个记录的序列为 { R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn } 这些关键字相互之间可以进行比较，即在它们之间 存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn 按此固有关系将上式记录序列重新排列为 { Rp1, Rp2, …，Rpn } 的操作称作排序
@C语言描述 #define MAXSIZE 1000 //待排顺序表最大长度 typedef int Key Type //关键字类型为整数类型 /*水冰*米米**冰*米*米水冰*米水**冰水*水*米冰水*/ typedef struct f KeyType key: //关键字项 InfoType otherinfo //其它数据项 的} RetYpe; //记录类型 /**水冰*米水*冰*米米水*冰*冰水*水****水*/ t ypedef struct RcdType r[MAXSIZE+1];//r[0]闲置 int length //顺序表长度 6 SqList //顺序表类型 计算机教研宦 第4页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第4页 C语言描述 #define MAXSIZE 1000 // 待排顺序表最大长度 typedef int KeyType; // 关键字类型为整数类型 /***********************************************/ typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项 } RcdType; // 记录类型 /***********************************************/ typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置 int length; // 顺序表长度 } SqList; // 顺序表类型
◎31排序的基本概念 内部排序 若整个排序过程不需要访问外存便能完成,则称 此类排序问题为内部排序; 外部排序 反之,若参加排序的记录数量很大,整个序列的 排序过程不可能在内存中完成,则称此类排序问题为 外部排序。 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第5页 3.1 排序的基本概念 • 内部排序 若整个排序过程不需要访问外存便能完成，则称 此类排序问题为内部排序； • 外部排序 反之，若参加排序的记录数量很大，整个序列的 排序过程不可能在内存中完成，则称此类排序问题为 外部排序