南京航空航天大学：《数据结构》课程教学资源（PPT课件讲稿）第十章 排序

教育部—微软精品课程建设项目 第十章排序 南京航空航天大学数据结构课题组版权所有

第十章 排序

教育部—微软精品课程建设项目 10.1概述 10.2插入排序 10.3快速排序 10.4选择排序 10.5归并排序 10.6基数排序 10.7各种排序方法的综合比较 10.8外部排序 南京航空航天大学数据结构课题组版权所有

10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种排序方法的综合比较 10.8 外部排序

教育部—微软精品课程建设项目 10.1概述 、排序的定义 、内部排序和外部排序 三、内部排序方法的分类 南京航空航天大学数据结构课题组版权所有

10.1 概 述 一、排序的定义 二、内部排序和外部排序 三、内部排序方法的分类

教育部—微软精品课程建设项目 、什么是排序? 排序是计算机内经常进行的一种操作, 其目的是将一组“无序”的记录序列调 整为“有序”的记录序列。 例如:将下列关键字序列 52,49,80,36,14,58,61,23,97,75 调整为 14,23,36,49,52,58,61,75,80, 南京航空航天大学数据结构课题组版权所有

一、什么是排序？ 排序是计算机内经常进行的一种操作， 其目的是将一组“无序”的记录序列调 整为“有序”的记录序列。 例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

教育部—微软精品课程建设项目 般情况下, 假设含n个记录的序列为{R1,R2,…Rn} 其相应的关键字序列为{K1,K2,…,Kn} 这些关键字相互之间可以进行比较,即在 它们之间存在着这样一个关系 Kn1≤Kn≤.≤K p pn 按此固有关系将上式记录序列重新排列为 &R pIpe Ron i pI 的操作称作排序。 京航空航天学给题组以有

一般情况下， 假设含n个记录的序列为{ R1 , R2 , …， Rn } 其相应的关键字序列为 { K1 , K2 , …，Kn } 这些关键字相互之间可以进行比较，即在 它们之间存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn 按此固有关系将上式记录序列重新排列为 { Rp1, Rp2, …，Rpn } 的操作称作排序

教育部—微软精品课程建设项目 二、内部排序和外部排序 若整个排序过程不需要访问外存便 能完成,则称此类排序问题为内部排 序 反之,若参加排序的记录数量很大, 整个序列的排序过程不可能在内存中 完成,则称此类排序问题为外部排序 京航空航天学给题组以有

二、内部排序和外部排序 若整个排序过程不需要访问外存便 能完成，则称此类排序问题为内部排 序； 反之，若参加排序的记录数量很大， 整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序

教育部—微软精品课程建设项目 三、内部排序的方法 内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。 有序序列区无序序列区 经过一趟排序 有序序列区无序序列区 南京航空航天大学数据结构课题组版权所有

三、内部排序的方法 内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。 经过一趟排序 有序序列区 无 序 序 列 区 有序序列区 无 序 序 列 区

教育部—微软精品课程建设项目 基于不同的“扩大”有序序列长 度的方法,内部排序方法大致可分 下列几种类型 插入类交换类选择类 归并类其它方法 南京航空航天大学数据结构课题组版权所有

基于不同的“扩大” 有序序列长 度的方法，内部排序方法大致可分 下列几种类型： 插入类 交换类 选择类 归并类 其它方法

待排记录的数据类型定义如下 # define maxsize1000∥待排顺序表最大长度 typedef int KeyType;∥关键字类型为整数类型 typedef struct i Key Type key; ∥关键字项 InfoType otherinfo;∥其它数据项 3 RetYpe, ∥记录类型 typedef struct t RcdType rMAXSIZE+1;∥r10闲置 int lengthe ∥顺序表长度 3 Sqlist ∥顺序表类型 使京航空航天大学数握结课题组败伙有

待排记录的数据类型定义如下: #define MAXSIZE 1000 // 待排顺序表最大长度 typedef int KeyType; // 关键字类型为整数类型 typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项 } RcdType; // 记录类型 typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置 int length; // 顺序表长度 } SqList; // 顺序表类型

教育部—微软精品课程建设项目 1插入类 将无序子序列中的一个或几 个记录“插入”到有序序列中, 从而增加记录的有序子序列的长 度 京航空航天学给题组以有

1. 插入类 将无序子序列中的一个或几 个记录“插入”到有序序列中， 从而增加记录的有序子序列的长 度