第十章内部排序 10概述 口102插入排序 日1021直接插入排序 口10.3h础排序 103交换排序(快速排序) 口104选择排序 口1041简单选择排序 口1043堆排序 0105归并排序 106基数排序 10各种排序方法的比较讨论
第十章 内部排序 10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.3 shell排序 10.3 交换排序（快速排序） 10.4 选择排序 10.4.1 简单选择排序 10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.7 各种排序方法的比较讨论
101内部排序概述 口排序( Sorting) 将数据元素(或记录)的一个任意序列,重新排列成 个按关键字有序的序列。 口排序方法的稳定性: 对关键字相同的数据元素,排序前后它们的领先关 系保持不变,则称该排序方法是稳定的。反之, 该排序方法是不稳定的。 内部排序 待排序记录存放在计算机的内存中进行排序 口外部排序 待排序记录的数量很大,以致内存一次不能容纳全 部记录,在排序过程中尚需对外存进行访问的排序
10.1 内部排序概述 排序(Sorting): • 将数据元素(或记录)的一个任意序列,重新排列成 一个按关键字有序的序列。 排序方法的稳定性： • 对关键字相同的数据元素，排序前后它们的领先关 系保持不变，则称该排序方法是稳定的。反之，称 该排序方法是不稳定的。 内部排序 • 待排序记录存放在计算机的内存中进行排序。 外部排序 • 待排序记录的数量很大，以致内存一次不能容纳全 部记录，在排序过程中尚需对外存进行访问的排序
排序的分类 口按排序过程依据的不同原则进行分类: 插入排序 交换排序 选择排序 归并排序和 基数排序 按工作量分类,可以分为三类: (1)简单的排序方法,其时间复杂度为0(n2) (2)先进的排序方法,其时间复杂度为0(nlog2n) (3)基数排序,其时间复杂度为0(dn)
排序的分类 按排序过程依据的不同原则进行分类： • 插入排序、 • 交换排序、 • 选择排序、 • 归并排序和 • 基数排序 按工作量分类，可以分为三类： • (1)简单的排序方法,其时间复杂度为O(n2); • (2)先进的排序方法,其时间复杂度为O(nlog2n); • (3)基数排序，其时间复杂度为O(dn);
排序的基本操作和 记录的存储方式 口排序过程中需要的两种基本操作 (1)比较关键字的大小 (2)将记录从一个位置移至另一个位置 待排序记录序列可有下列三种存储方式 日(1)记录存放在一组连续的存储单元中;类似于线性表 的顺序存储结构,记录次序由存储位置决定,实现排序需 移动记录。 (2)记录存放在静态链表中;记录次序由指针指示,实 现排序不需移动记录,仅需修改指针。一链排序 (3)记录本身存放在一组连续的存储单元中,同时另设 指示各个记录存储位置的地址向量,排序过程中不移动记 录本身,而移动地址向量中相应记录的地址。排序结束后 再根据地址调整记录的存储位置。一地址排序
排序的基本操作和 记录的存储方式 排序过程中需要的两种基本操作： • （1）比较关键字的大小； • （2）将记录从一个位置移至另一个位置。 待排序记录序列可有下列三种存储方式： （1）记录存放在一组连续的存储单元中；类似于线性表 的顺序存储结构，记录次序由存储位置决定，实现排序需 移动记录。 （2）记录存放在静态链表中；记录次序由指针指示，实 现排序不需移动记录，仅需修改指针。---链排序 （3）记录本身存放在一组连续的存储单元中，同时另设 指示各个记录存储位置的地址向量，排序过程中不移动记 录本身，而移动地址向量中相应记录的地址。排序结束后 再根据地址调整记录的存储位置。---地址排序
待排序记录的数据类型 口# define maXsize20 o typedef int KeyType o typedef struct t o KeyType key InfoType otherinfo 口} RetYpe; o typedef struct 口 RedType r LMAXSIZE+1 int length D/SqList
待排序记录的数据类型 #define MAXSIZE 20 typedef int KeyType; typedef struct{ KeyType key; InfoType otherinfo; }RcdType; typedef struct{ RedType r[MAXSIZE+1]; int length; }SqList;