数据结构_数据结构10.ppt

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