第十章排序 基本概念 插入排序 快速排序 选择排序 归并排序 ·基教排序 10.1概念 >排序 构 设含有n个记录的文件{R1R2,Rn}, 之其相应的关键字为{K,K2Kn},需确定 1,2,…,n的一种排列p1,p2,…,pn,使其相应 部的关键字满足如下的非递减(或非递增)关 系Kn=K2=.,<=Km,从而使序列 {Rp,Rp2…,Rmn}按关键字有序,该过程称为 排序
1 第十章 排序 • 基本概念 • 插入排序 • 快速排序 • 选择排序 • 归并排序 • 基数排序 数 据 结 构 之 内 部 排 序 2 10. 1 概念 ¾排序 设含有n个记录的文件{R1,R2,...,Rn}， 其相应的关键字为{K1,K2,...,Kn}，需确定 1,2, …, n的一种排列p1,p2, …, pn,使其相应 的关键字满足如下的非递减(或非递增)关 系 Kp1<=Kp2<=…<=Kpn, 从而使序列 {Rp1,Rp2,...,Rpn}按关键字有序, 该过程称为 排序
据结构 排序的稳定性 对所有的K=K(i≠j,若排序前R领先于 排序后R仍领先于R,则称该排序方法是稳 定的反之,若可能使排序后的序列中R领先 于R1,则称所用的排序方法为不稳定的 部 稳定性是对序列中的两个相同关键字的 记录在初始序列和最终有序序列中相对位置( 即领先关系)是否变化的描述。 据>内部排序和外部排序 构 内部排序:待排序文件的全部记录存放在 内存进行的排序,称为内部排序。 外部排序:待排序记录的数量很大,以致 内存一次不能容纳全部记录,排序过程中 内部排序 需要进行内外存数据交换的排序,称为外 部排序
2 数 据 结 构 之 内 部 排 序 3 ¾ 排序的稳定性 对所有的Ki=Kj (i≠j), 若排序前Ri领先于 Rj, 排序后Ri仍领先于Rj, 则称该排序方法是稳 定的；反之，若可能使排序后的序列中Rj领先 于Ri, 则称所用的排序方法为不稳定 的。 稳定性是对序列中的两个相同关键字的 记录在初始序列和最终有序序列中相对位置( 即领先关系)是否变化的描述。 数 据 结 构 之 内 部 排 序 4 ¾ 内部排序和外部排序 ¾ 内部排序：待排序文件的全部记录存放在 内存进行的排序，称为内部排序。 ¾ 外部排序：待排序记录的数量很大, 以致 内存一次不能容纳全部记录, 排序过程中 需要进行内外存数据交换的排序，称为外 部排序
据结构 内排序分类 按排序过程依据的原则分为:插入排序 交换排序 选择排序 归并排序 部 计数排序 按排序过程所需的工作量分:简单排序O(mn2) 先进排序O( nlog n) 基数排序O(d.n) 存储形式 数据结构 连续存放在地址连续的一组存储单元上 静态链表存储形式。 待排记录存放在一组地址连续的存储单 元中,同时另设一个指示各个记录存储位置 内部排序 的地址向量,在排序过程中不移动记录本身, 只修改这些记录的地址,在排序结束之后在 按照地址向量中的值调整记录的存储位置
3 数 据 结 构 之 内 部 排 序 5 ¾ 内排序分类 按排序过程依据的原则分为：插入排序 交换排序 选择排序 归并排序 计数排序 按排序过程所需的工作量分：简单排序 O(n2) 先进排序 O(nlog n) 基数排序 O(d．n) 数 据 结 构 之 内 部 排 序 6 ¾ 存储形式 ¾ 连续存放在地址连续的一组存储单元上。 ¾ 静态链表存储形式。 待排记录存放在一组地址连续的存储单 元中，同时另设一个指示 各个记录存储位置 的地址向量，在排序过程中不移动记录本身， 只修改这些记录的地址，在排序结束之后在 按照地址向量中的值调整记录的存储位置
数>排序算法的性能度量 结 排序算法的时间复杂度: 记录移动次数、比较次数; 空间复杂度; >排序方法的稳定性 内部排序 #define maXsize 100 ∥顺序表的长度 据 Typedef int Key Type; ∥关键字类型为整数 类型 构 ypedef struct{ Key Type key;/关键字项 InfoType otherinfo; )其它数据项 A JRedType ∥记录类型 s type struct( RedType r[MAXSIZE+1; 排 r10空作为哨兵 int length; ∥顺序表长度 JSlIst ∥顺序表类型
4 数 据 结 构 之 内 部 排 序 7 ¾ 排序算法的性能度量 ¾ 排序算法的时间复杂度： 记录移动次数、比较次数； ¾ 空间复杂度； ¾ 排序方法的稳定性 数 据 结 构 之 内 部 排 序 8 #define MAXSIZE 100 //顺序表的长度 Typedef int KeyType; //关键字类型为整数 类型 Typedef struct{ KeyType key; //关键字项 InfoType otherinfo; //其它数据项 }RedType; //记录类型 type struct { RedType r[MAXSIZE+1]; //r[0]空作为哨兵 int length; //顺序表长度 }SqList; //顺序表类型
10.2插入排序 >直接插入排序 基本操作:是将一个记录插入到已排 好序的有序表中,从而得到一个新的 记录数增1的有序表。 整个排序过程:先将原序列中的第 部 个记录看成是一个有序的子序列,然 序 后,从第2个记录起逐个进行插入,直 至整个序列变成按关键字非递减有序 序列为止 例:已知关键字为{49386597761327 数49},采用直接插入排序方法对其进行排序 据 结初始关键字:(49)38659776132749 构 i=2:(38)(3849)659776132749 65)9776132749 i=4:(97)638496597)76132749 排 i=5:(76)(38 657697)132749 序 i=6:(13)(133849657697)2749 (27)(13273849657697)49 i=8:(49)(1327384949657697)
5 数 据 结 构 之 内 部 排 序 9 10. 2 插入排序 ¾ 直接插入排序： ¾ 基本操作：是将一个记录插入到已排 好序的有序表中，从而得到一个新的 记录数增1的有序表。 ¾ 整个排序过程：先将原序列中的第一 个记录看成是一个有序的子序列，然 后，从第2个记录起逐个进行插入，直 至整个序列变成按关键字非递减有序 序列为止。 数 据 结 构 之 内 部 排 序 10 例：已知关键字为{ 49 38 65 97 76 13 27 49}，采用直接插入排序方法对其进行排序。 初始关键字： （49） 38 65 97 76 13 27 49 i=2: (38) (38 49) 65 97 76 13 27 49 i=3: (65) (38 49 65) 97 76 13 27 49 i=4: (97) (38 49 65 97) 76 13 27 49 i=5: (76) (38 49 65 76 97) 13 27 49 i=6: (13) (13 38 49 65 76 97) 27 49 i=7: (27) (13 27 38 49 65 76 97) 49 i=8: (49) (13 27 38 49 49 65 76 97)
void Insertsort(sqlist < for(i=2; i空间上,只需i,j两个整型变量和一个记录的 数据结构 辅助空间r0l,r0作为“监视哨”,控制待插入 元素相对于有序子文件为最小时WHIE循环 的结束,同时也用于暂存待插入元素。 时间上,只包含比较关键字和移动记录两种 操作 当待排序初始文件按关键字非递减有序(正序)时: 内部排序 >对每个记录只进行一次比较,整个排序过程共 进行了∑1=n-1次比较(最少); 每个记录都要进行r移到r0和r0移到rj+1两 次移动,因此共移动2(n-1次(最少)
6 数 据 结 构 之 内 部 排 序 11 void InsertSort(SqList &L){ for(i=2; i<=L.length;++i) if(L. r[i]. key<L.r[i-1]. key){ L.r[0]=L. r[i]; //复制哨兵// for(j=i-1;L. r[0]. key<L. r[j]. key;--j) L. r[j+1]=L. r[ j ]; L. r[j+1]=L. r[ 0 ]; } } //O( n*n ) 性能分析：（1）时间复杂度：O(n*n) （2） 空间复杂度：O(1) （3）排序方法是稳定的 数 据 结 构 之 内 部 排 序 12 ¾ 算法分析 ¾空间上，只需i，j两个整型变量和一个记录的 辅助空间r[0], r[0]作为“监视哨”，控制待插入 元素相对于有序子文件为最小时WHILE循环 的结束，同时也用于暂存待插入元素。 ¾时间上，只包含比较关键字和移动记录两种 操作。 ¾当待排序初始文件按关键字非递减有序(正序)时： ¾ 对每个记录只进行一次比较，整个排序过程共 n 进行了∑1=n-1次比较(最少)； i=2 ¾ 每个记录都要进行r[i]移到r[0]和r[0]移到r[j+1]两 次移动，因此共移动2(n-1)次(最少)
当待排序文件按关键字非递增有序逆序) 时 据结构 >记录r[j(=2,3,n)均要和前i-1个记录及r0进 行比较,整个排序过程共进行了 ∑i=(n+2)(n-1)/2次比较(最多); 移动记录次数:每个记录都要进行r订移动到 r0和r移动到r+1两次移动,另外当 内部排序 r[ i-key直接插入排序的时间复杂度为O(n2); 直接插入排序是稳定的这一点由过程 内部排序 中WHIE语句的条件“<”保证的)。 14
7 数 据 结 构 之 内 部 排 序 13 ¾当待排序文件按关键字非递增有序(逆序) 时 ¾记录r[i](i=2,3,...n)均要和前i-1个记录及r[0]进 行比较，整个排序过程共进行了 n ∑ i=(n+2)(n-1)/2次比较(最多)； i=2 ¾移动记录次数：每个记录都要进行r[i]移动到 r[0]和r[0]移动到r[j+1]两次移动，另外当 r[i].key＜r[j].key时，还将r[j]移动到r[j+1]， 所以，当初始文件为逆序时移动记录次数最 多, 为 n ∑ (i-1)+2(n-1)=(n+4)(n-1)/2次(最多)。 数 据 结 构 之 内 部 排 序 14 ¾结论 ¾直接插入排序的效率与待排文件的关 键字排列有关； ¾直接插入排序的时间复杂度为O(n2)； ¾直接插入排序是稳定的(这一点由过程 中WHILE语句的条件“＜”保证的)
折半插入排序 N Void BInsertSort( Sqlist &l)( 据结构 for(i=2; i=high+l;--j)Lr[j+1=Lrl; L rhigh+1FL.r[o: >2-路插入排序 据 例:对初始关键字为{49,38,65,97,76,13,27 49}的序列进行2-路插入排序。 构 解:其2路插入排序的过程如下 初始关键字:4938659776132749 1:(49 内i=2: (38) 排 (4965) 个fnal 个frst
8 数 据 结 构 之 内 部 排 序 15 ¾ 折半插入排序 Void BInsertSort ( Sqlist &L) { for ( i=2; i=high+1; --j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; } } 数 据 结 构 之 内 部 排 序 16 ¾ 2-路插入排序 例：对初始关键字为{49，38，65，97，76，13，27， 49} 的序列进行2-路插入排序。 解：其2路插入排序的过程如下 初始关键字： 49 38 65 97 76 13 27 49 i=1: (49) first↑ ↑final i=2: (49) (38) ↑final ↑first i=3: (49 65) (38) ↑final ↑first
i=4:(496597) (38) 个fna ↑frst 结i=5:(49657697 个fnal 个frst i=6:(49657697) (1338) 个f 部i=7: 49657697) (132738) 序 个fnal 个frst i-8:(4949657697132738) 个 个frst 与折半插入排序相比,2路插入排序可以减 据 构 少记录移动的次数,但不能避免记录的移动。 此外需要N个额外的存储空间。并且如果Lr 是待排序记录中关键字最小(或最大)的记录 排 时,2路排序就没有优越性可言了。 18
9 数 据 结 构 之 内 部 排 序 17 i=4: (49 65 97) (38) ↑final ↑first i=5: (49 65 76 97) (38) ↑final ↑first i=6: (49 65 76 97) (13 38) ↑final ↑first i=7: (49 65 76 97) (13 27 38) ↑final ↑first i=8: (49 49 65 76 97 13 27 38) ↑final ↑first 数 据 结 构 之 内 部 排 序 18 与折半插入排序相比，2路插入排序可以减 少记录移动的次数，但不能避免记录的移动。 此外需要N个额外的存储空间。并且如果L.r[1] 是待排序记录中关键字最小（或最大）的记录 时，2路排序就没有优越性可言了
表插入排序 如果希望在排序过程中不移动记录,只有改变存储结构,进行表插 据结构 入排序。表插入排序的存储结构用C语言表述如下: #define SIZe 100 静态连表容量 typedef struct RetYpe re /记录项 next 指针项 内部排序 sYNOde 表结点类型 typedef struct( SLNode rSIZE: /0号单元为表头结点 19 nt length 链表当前长度 SLinkList Type /静态链表类型 其实现方法 数据结构 首先将静态链表中数组下标为“1”的分量(结点)和表 头结点构成一个循环链表(表头接点记录的关键字取最 大的整数 MAXINT),然后依次将下标为“2”至“n”的 分量(结点)按记录关键字非递减有序插入到循环链表 中 例:采用表插入排序将下面的序列49,38,65 97,76,13,27,49按从小到大的顺序排列
10 数 据 结 构 之 内 部 排 序 19 ¾ 表插入排序 如果希望在排序过程中不移动记录，只有改变存储结构，进行表插 入排序。表插入排序的存储结构用C语言表述如下： #define SIZE 100 //静态连表容量 typedef struct{ RcdType rc; //记录项 int next; //指针项 }SLNode; //表结点类型 typedef struct{ SLNode r[SIZE]; //0号单元为表头结点 int length; //链表当前长度 }SLinkListType; //静态链表类型 数 据 结 构 之 内 部 排 序 20 其实现方法： 首先将静态链表中数组下标为“1”的分量（结点）和表 头结点构成一个循环链表（表头接点记录的关键字取最 大的整数MAXINT），然后依次将下标为“2”至“n”的 分量（结点）按记录关键字非递减有序插入到循环链表 中。 例：采用表插入排序将下面的序列{49，38，65， 97，76，13，27，49}按从小到大的顺序排列