1、第十章排序10.1 概述10.2 插入排序10.3 快速排序10.4 堆排序10.5 归并排序10.6 基数排序10.7 各种排序方法的综合比较10.8 外部排序10.1 概 述一、排序的定义二、内部排序和外部排序三、内部排序方法的分类一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组 “无序 ”的记录序列调整为 “有序 ”的记录序列。例如： 将下列关键字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为14, 23, 36, 49, 52, 58, 61 ,75, 80, 97一般情况下，假设含 n个记录的序列为 R1, R2, ， Rn 其
2、相应的关键字序列为 K1, K2, ， Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ：Kp1 Kp2 Kpn按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ， Rpn 的 操作 称作 排序 。二、内部排序和外部排序若 整个排序过程 不需要访问外存 便能完成，则称此类排序问题 为 内部排序 ； 反之，若参加排序的记录数量很大，整个序列的排序过程 不可能在内存中完成 ，则称此类排序问题 为 外部排序 。三、内部排序的方法内部排序的过程是一个 逐步扩大记录的 有序序列长度 的过程。经过一趟排序有序序列区 无 序 序 列 区有序序列区 无 序 序 列 区基于不同的
3、“扩大 ” 有序序列长度的 方法，内部排序方法 大致可分下列几种类型：插入类 交换类 选择类归并类 其它方法待排记录的数据类型定义如下 :#define MAXSIZE 1000 / 待排顺序表最大长度typedef int KeyType; / 关键字类型为整数类型typedef struct KeyType key; / 关键字项InfoType otherinfo; / 其它数据项 RcdType; / 记录类型typedef struct RcdType rMAXSIZE+1; / r0闲置int length; / 顺序表长度 SqList; / 顺序表类型1. 插入类将无序子序列中的 一个或几个记录 “插入 ”到有序序列中，从而增加记录的有序子序列的长度。
