浙江大学：《数据结构与算法》第十章 内部排序

第十章内部排序 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;

102插入排序 1021直接插入排序 例:序列为{49,38,65,97,76,13,27,49 (49),38,65,97,76,13,27,49} 0(38){(38,49),65,97,76,13,27,49} 日(65){(38,49,65),97,76,13,27,49 (97){(38,49,65,97),76,13,27,49} (76){(38,49,65,76,97),13,27,49} (13){(13,38,49,65,76,97),27,49} 口(27){(13,27,38,49,65,76,97),49 (49){(13,27,38,49,49,65,76,97)}

10.2 插入排序 10.2.1 直接插入排序 例：序列为{49，38，65，97，76，13，27，49} {(49)，38，65，97，76，13，27，49} (38) {(38，49)，65，97，76，13，27，49} (65) {(38，49，65)，97，76，13，27，49} (97) {(38，49，65，97)，76，13，27，49} (76) {(38，49，65，76，97)，13，27，49} (13) {(13，38，49，65，76，97)，27，49} (27) {(13，27，38，49，65，76，97)，49} (49) {(13，27，38，49，49，65，76，97)}

直接插入排序算法 void InsertSort(sqlist &l) i for(i-2, K<=L length; ++i) if(T(L ri].key, L r[i-1. key)) Lr[0]=L.r[i]; ∥复制为哨兵 for(Fi-1; LT(L r[O).key, Lri]. key);--j L r[j+1-Lrll; ∥记录后移 Lr[+1]=L.r[o] ))// InsertSort 时间:最坏情形判断与移动各接近n(n+1)2 最好情形判断n次,无移动;故时间复杂度:O(n2) 间:一个辅助空间

直接插入排序算法 void InsertSort(SqList &L) { for(i=2; i<=L.length; ++i) if ( LT(L.r[i].key, L.r[i-1].key) ){ L.r[0] = L.r[i]; // 复制为哨兵 for(j=i-1; LT(L.r[0].key, L.r[j].key); --j) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; }} // InsertSort 时间：最坏情形判断与移动各接近 n(n+1)/2; 最好情形判断n次，无移动；故时间复杂度：O(n2 ) 空间：一个辅助空间

1022She11排序算法 口基木思想: 口先将整个待排序记录序列分割成若干 子序列分别进行直接插入排序,待整个 序列“基本有序”时,再对全体记录进 次直接插入排序 口算法复杂度:0(n32

10.2.2 Shell排序算法 基本思想： 先将整个待排序记录序列分割成若干 子序列分别进行直接插入排序，待整个 序列“基本有序”时，再对全体记录进 行一次直接插入排序。 算法复杂度：O(n3/2)

She11排序举例(非稳定的) 例 {49,38,65,97,76,13,27,49,55,04} 增量取5:49 13 38 65 49 97 55 76 04 趟结果{13,27,49,55,04,49,38,65,97,76} 增量取3:13 55 38 76 27 04 65 49 49 97 二趟结果{13,04,49,38,27,49,55,65,97,76} 增量取1:13,04,49,38,27,49,55,65,97,76 三趟结果{04,13,27,38,49,49,55,65,76,97

Shell排序举例（非稳定的） 二趟结果{13，04，49，38，27，49，55，65，97，76} 增量取1：13，04，49，38，27，49，55，65，97，76 三趟结果{04，13，27，38，49，49，55，65，76，97} 一趟结果{13，27，49，55，04，49，38，65，97，76} 增量取3：13 55 38 76 27 04 65 49 49 97 例： {49，38，65，97，76，13，27，49，55，04} 增量取5： 49 13 38 27 65 49 97 55 76 04

103交换排序 1冒泡排序(其时间复杂度0(n2)) 例 49383838381313 38494949132727 65656513273838 977613274949 7613274949 13274965 274976 4997 初第第第第第第 始 关递趟超 排排 键序序序序 字后后后

10.3 交换排序 1. 冒泡排序（其时间复杂度O(n2)） 初 始 关 键 字 第 一 趟 排 序 后 第 二 趟 排 序 后 第 三 趟 排 序 后 第 四 趟 排 序 后 第 五 趟 排 序 后 第 六 趟 排 序 后 例： 49 38 38 38 38 13 13 38 49 49 49 13 27 27 65 65 65 13 27 38 38 97 76 13 27 49 49 76 13 27 49 49 13 27 49 65 27 49 76 49 97