第10章内部排序.ppt

插入排序
快速排序
堆排序
归并排序
基数排序
各种排序方法的综合比较
第十章内部排序
概述
本章小结
习题十
概述
一、排序的定义
二、内部排序和外部排序
三、内部排序方法的分类
一、什么是排序?
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
例如:将下列关键字序列
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 }
这些关键字相互之间可以进行比较,即在
它们之间存在着这样一个关系:
Kp1≤Kp2≤…≤Kpn
按此固有关系将上式记录序列重新排列为
{ Rp1, Rp2, …,Rpn }
的操作称作排序。
二、内部排序和外部排序
若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序;
反之,若参加排序的记录数量很大,
整个序列的排序过程不可能在内存中
完成,则称此类排序问题为外部排序。
三、内部排序的方法
内部排序的过程是一个逐步扩大
记录的有序序列长度的过程。
经过一趟排序
有序序列区
无序序列区
有序序列区
无序序列区
基于不同的“扩大”有序序列长度的方法,内部排序方法大致可分下列几种类型:
插入类
交换类
选择类
归并类
其它方法
待排记录的数据类型定义如下:
#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. 插入类
将无序子序列中的一个或几个记录“插入”到有序序列中,从而增加记录的有序子序列的长度。
2. 交换类
通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。