数据结构复习

2021.4.17 UPD：除坑外一轮复习完成

第1章绪论

1.1 什么是数据结构

1.数据结构是研究 非数值计算 程序设计问题中 计算机的操作对象 以及它们之间的 关系和操作 等的学科

1.2 基本概念和术语

1.数据元素：由若干个数据项组成，数据项是数据不可分割的最小单位

2.数据对象：性质相同的数据元素的集合

3.数据结构：相互之间存在一种或多种特定关系的数据元素的集合

4.数据元素的4类基本结构：集合、线性、树、图

5.数据结构形式定义通常是一个二元组 $(D,S)$ ， $D$ 是数据元素的有限集， $S$ 是定义在 $D$ 上关系的有限集，这里的关系是逻辑关系，也是数据的逻辑结构

6.数据结构在计算机中的表示是数据的物理结构，也称存储结构，有顺序存储结构和链式存储结构

7.顺序存储结构借助元素在存储器的相对位置表示数据元素之间的逻辑关系

8.链式存储结构借助指示元素存储地址的指针表示数据元素之间的逻辑关系

9.数据类型是一个值的集合和定义在这个值集上的一组操作的总称，例如C语言中的整型变量，值集为某个区间上的整数和定义在其上的加减乘除取模等算术运算

10.抽象数据类型（ADT）：数据类型的数学抽象

11.抽象数学类型大体分为3种类型：原子类型、固定聚合类型和可变聚合类型。原子类型的变量值是不可分解的，固定聚合类型其值由确定数目的成分按某种结构组成，可变聚合类型与固定聚合类型的区别是数目不确定，后两种类型可统称为结构类型

12.抽象数据类型可以用三元组 $(D,S,P)$ 表示，其中 $D$ 是数据对象， $S$ 是 $D$ 上的关系集， $P$ 是对 $D$ 的基本操作集

1.3 抽象数据类型的表示与实现

1.4 算法和算法分析

1.算法的5个重要特性：有穷性、确定性、可行性、输入和输出

2.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求

3.算法效率的度量一般采用事前分析估算的方法，撇开与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小只依赖于问题的规模，以一个算法的基本操作重复执行的次数作为算法的时间量度，例如矩阵乘法 $T(n)=O(n^3)$ ，表示随问题规模 $n$ 的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，称作算法的渐近时间复杂度

4.时间复杂度 $O$ 的形式定义可以类比极限的定义

5.有时基本操作重复执行的次数随问题的输入数据集不同而不同，例如冒泡排序算法，这时需要考虑它对所有可能的输入数据集的期望值，此时的时间复杂度称为算法的平均时间复杂度，但是一般讨论算法的最坏时间复杂度

6.实践时估计算法的执行时间可以采用实际时间与时间复杂度的相乘的方法

7.算法的存储空间需求一般只需要分析除输入和程序之外的额外空间

第2章线性表

2.1 线性表的类型定义

1.线性结构的特点：①存在唯一一个称作“第一个”的数据元素②存在唯一一个称作“最后一个”的数据元素③除第一个之外每个数据元素均只有一个前驱④除最后一个之外每个数据元素均只有一个后继

2.2 线性表的顺序表示和实现

1.顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素

2.线性表插入元素移动次数期望 $\frac {n}{2}$ ，删除元素移动次数期望 $\frac {n-1}{2}$

3.求两个线性表的并集时间复杂度 $O(nm)$ ，合并两个有序线性表时间复杂度 $O(n+m)$

2.3 线性表的链式表示和实现

1.链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素

2.每个结点包含数据域和指针域

3.整个链表的存储必须从头指针开始，头指针指示链表中的第一个结点

4.用一维数组可以实现静态链表，类比next数组存储图

5.循环链表：最后一个结点的指针域指向头结点，判断是否遍历过一遍用当前结点是否等于头结点

6.循环链表设置尾指针可以 $O(1)$ 合并两个线性表

2.4 一元多项式的表示及相加

第3章栈和队列

3.1 栈

1.栈和队列是操作受限的线性表

2.栈在使用过程中所需最大空间大小难以估计，一般初始化设空栈时不限定栈的最大容量，一般先为栈分配一个基本容量，当栈的空间不够使用时再逐段扩大

3.非空栈的栈顶指针始终在栈顶元素的下一个位置上

3.2 栈的应用举例

1.输入缓冲区为栈结构

3.3 栈与递归的实现

3.4 队列

1.双端队列是限定插入和删除操作在表的两端进行的线性表

2.队列的头指针始终指向头结点，头指针的next指向队首元素

3.循环队列头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置

4.循环队列只凭front==rear无法判断队列空间是否满，可有两种处理方法：①另设一个标志位以区别队列是空还是满②少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置上”作为队列满状态的标志

3.5 离散事件模拟

第4章串

4.1 串类型的定义

1.串是由零个或多个字符组成的有限序列

4.2 串的表示与实现

1.定长顺序存储表示：用一组地址连续的存储单元存储串值的字符序列，超过预定义长度的串值则被“截断”，在C语言中以\0表示串值的终结

2.堆分配存储表示：同上，但存储空间在程序执行过程中动态分配，C语言中在堆存储区利用malloc函数为每一个新产生的串分配一块实际串长所需的存储空间

3.块链存储表示：链表存储，每个结点可以是一个或多个字符，多个字符若不能被整除则以#补全，一般情况下不建立双向链表，除头指针外附设尾指针，方便进行联结操作

4.存储密度=串值所占的存储位/实际分配的存储位，存储密度小，运算处理方便，存储占用量大

4.3 串的模式匹配算法

1.KMP算法（坑）

第5章数组和广义表

5.1 数组的定义

1.抽象数据类型数组的定义n维数组每一维维数不一定相同

2.数组除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作，一般不作插入或删除操作

5.2 数组的顺序表示和实现

1.二维数组有两种存储方式：以行序和以列序为主序的存储方式，特别地，Fortran语言默认以列序为主序的存储结构

5.3 矩阵的压缩存储

1.值相同的元素或者零元素在矩阵中的分布有一定规律，这类矩阵为特殊矩阵，反之为稀疏矩阵

2.对称矩阵可以用一维数组 $sa[n(n+1)/2]$ 与矩阵中的非零元素进行一一对应

3.三对角矩阵与对称矩阵的区别为主对角线有3条对角线全是非零元素

4.稀疏矩阵中 $\delta =\frac{t}{m\times n}$ ，表示 $m\times n$ 矩阵中有 $t$ 个非零元素， $\delta$ 为矩阵的稀疏因子，通常认为 $\delta \leq 0.05$ 时称为稀疏矩阵

5.稀疏矩阵中的非零元素可用三元组 $(i,j,a_{ij})$ 唯一确定，可用三元组顺序表和十字链表存储

5.4 广义表的定义

1.广义表是线性表的推广，广义表中的元素可以是单个元素也可以是广义表，称为广义表的原子和子表，当广义表非空时，称第一个元素为表头，其余元素为表尾

2.递归的表长度为本身长度

3.任何一个非空列表其表头可能是原子也可能是列表，而其表尾必定为列表

5.5 广义表的存储结构

5.6 m元多项式的表示

5.7 广义表的递归算法

第6章树和二叉树

6.1 树的定义和基本术语

1.树是n个结点的有限集，当 $n>1$ 时，其余结点可分为 $m$ 个互不相交的有限集 $T_1,T_2,\cdots ,T_m$ ，其中每一个集合本身又是一棵树，并且称为根的子树

2.树的结构定义是一个递归的定义，是树的固有特性

3.树的其他表示形式：①嵌套集合②广义表③凹入表示法

4.树的结点包含一个数据元素及若干指向其子树的分支，结点拥有的子树数称为结点的度，度为0的结点称为叶子或终端结点，否则为非终端结点或分支结点，树的度是树内各结点度的最大值

5.如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树

6.森林是m棵互不相交的树的集合，可以用森林和树相互递归的定义来描述树

6.2 二叉树

1.二叉树的子树有左右之分，其次序不能任意颠倒

2.n个结点的二叉树互不相似的形态数满足卡特兰数，即 $f(n)=\frac{(2n)!}{n!(n+1)!}$ .

3.对任何一个二叉树T，如果其终端结点数为 $n_0$ ，度为2的结点数为 $n_2$ ，则 $n_0=n_2+1$ .

一般情况：对任何一个m叉树T，如果其终端结点数为 $n_0$ ，则 $n_0=\sum\limits_{i=2}^{m}(i-1)n_i+1$

4.具有n个结点的完全二叉树的深度为 $\lfloor log_2n \rfloor +1$ .

5.顺序存储结构用一组地址连续的存储单元依次自上而下从左至右存储完全二叉树上的结点元素，仅适用于存储完全二叉树

6.链式存储结构只包含数据域和左右指针域的为二叉链表，再加上双亲指针域的为三叉链表

7.链表的头指针指向二叉树的根结点，在含有n个结点的二叉链表中有n+1个空链域（根据第3条可以证明）

6.3 遍历二叉树和线索二叉树

1.层序遍历相当于bfs

2.当以二叉链表作为存储结构时，只能找到结点的左右孩子信息，不能直接得到结点在任一序列中的前驱、后继信息，要保存在遍历过程中得到的信息，在每个结点上增加两个指针域fwd和bkwd，分别指示结点在依任一次序遍历时得到的前驱和后继信息，这样做可以使得结构的存储密度大大降低

3.由n个结点的二叉链表的n+1个空链域用LTag、lchild来指示左孩子和前驱，同理RTag和rchild指示右孩子和后继，以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树为线索二叉树

4.在中序线索二叉树上遍历二叉树常数因子更小，不需要设栈

5.在二叉树的线索链表上添加一个头结点，lchild指向二叉树的根结点，rchild指向中序遍历最后一个结点，同时将中序遍历第一个结点lchild和最后一个结点rchild均指向头结点，建立了一个双向线索链表

6.4 树和森林

1.双亲表示法：每个结点附设一个指示器指示其双亲结点在链表中的位置，但这种表示法求结点的孩子需要遍历整个结构

2.孩子表示法：多重链表，每个结点多个指针域，若不增设degree指针域，n个结点度为k的树必有 $n(k-1)+1$ 个空链域，浪费很多空间，若增设degree指针域，则每个结点是不同构的，虽然节约存储空间但是操作不方便

3.孩子兄弟表示法：二叉链表作为树的存储结构，结点的两个链域分别指向第一个孩子结点和下一个兄弟结点，增设parent域能同时方便地求双亲和孩子

4.森林、树和二叉树的转换：孩子兄弟表示法

5.树和森林的遍历：将树和森林转换为等价的二叉树进行遍历得到的序列相同

6.5 树与等价问题

1.整节介绍的都是并查集

6.6 哈夫曼树及其应用

1.路径上的分支数目称为路径长度，树的路径长度是树根到每一结点的路径长度之和，树的带权路径长度为树中所有叶子结点的带权路径长度之和，即 $WPL=\sum\limits_{k=1}^n \omega _kl_k$ .

2.n个带权结点构造WPL最小的二叉树称为最优二叉树或哈夫曼树

3.哈夫曼编码：设计长短不一的编码（防止编码过长），必须任一字符的编码都不是另一个字符的编码的前缀，称作前缀编码

4.哈夫曼编码本质思想是贪心，类比合并果子

6.7 回溯法与树的遍历

1.求子集（dfs）和n皇后（回溯）

6.8 树的计数

1.6.2第2条

2.具有n个结点不同形态的树的数目 $t_n$ 和具有n-1个结点互不相似的二叉树数目相同，即 $t_n=b_{n+1}$ ，b满足卡特兰数

第7章图

7.1 图的定义和术语

1.图中的数据元素称为顶点，若 $<\upsilon,\omega>\in VR$ ，则 $<\upsilon,\omega>$ 表示从 $\upsilon$ 到 $\omega$ 的一条弧，称 $\upsilon$ 为弧尾， $\omega$ 为弧头，为有向图，若 $<\upsilon,\omega>\in VR$ 则必有 $<\omega,\upsilon>\in VR$ ，此时图为无向图

2.有 $\frac{1}{2}n(n-1)$ 条边的无向图为完全图，有 $n(n-1)$ 条弧的有向图为有向完全图，有很少边或弧（ $e<nlogn$ ）的图称为稀疏图，反之为稠密图，带权的图称为网

3.顶点 $\upsilon$ 为头的弧的数目称为 $\upsilon$ 的入度，记为 $ID(\upsilon)$ ，以 $\upsilon$ 为尾的弧的数目称为 $\upsilon$ 的出度，记为 $OD(\upsilon)$ ，顶点的度记为 $TD(\upsilon)=ID(\upsilon)+OD(\upsilon)$ ，一般地，如果顶点 $\upsilon_i$ 的度记为 $TD(\upsilon_i)$ ，那么一个有n个顶点，e条边或弧的图，满足 $e=\frac{1}{2}\sum\limits_{i=1}^nTD(\upsilon_i)$

4.无向图 $G=(V,E)$ 中从顶点 $\upsilon$ 到顶点 $\upsilon'$ 的路径是一个顶点序列，第一个顶点和最后一个顶点相同的路径称为回路或环，序列中顶点不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路或简单环

5.无向图中两个顶点之间有路径则两点连通，若对于图中任意两个顶点连通则称图为连通图，无向图的极大连通子图为连通分量

6.连通的无向图只有一个连通分量，非连通的无向图可能有多个连通分量

7.有向图中任意两点连通则为强连通图，有向图的极大连通子图为有向图的强连通分量，一个连通图的生成树是一个极小连通子图

8.极大和极小连通子图依据边数来决定，在保证连通的条件下边数尽可能多或者少

9.有向图恰有一个顶点入度为0，其余顶点入度为1，则是一棵有向树，一个有向图的生成森林由若干棵有向树生成

7.2 图的存储结构

1.图的结构比较复杂，任意两点之间都可能存在联系，没有顺序影像的存储结构，但可以借助数组的数据类型表示元素之间的关系，常用邻接表、邻接多重表和十字链表来存储

2.数组表示法是采用邻接矩阵来表示图，构造一个具有n个顶点和e条边的无向网G的时间复杂度为 $O(n^2+e\times n)$

3.邻接表是图的链式存储结构，链域指示下一条边或弧的结点，数据域存储和边或弧相关的信息，第i个链表中的结点个数只是顶点 $\upsilon_i$ 的出度，求入度必须遍历整个邻接表，建立逆邻接表方便求入度，建立邻接表或逆邻接表的时间复杂度为 $O(n+e)$

4.十字链表可以看成是有向图的邻接表和逆邻接表结合起来得到的链表，有向图的每条弧和每个结点都对应一个结点，弧结点有尾域和头域，分别指示弧尾和弧头结点在图中的位置，hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧，info指向弧的相关信息，顶点结点firstin和firstout分别指向顶点为弧头或弧尾的第一个弧结点，data指向结点的相关信息，十字链表容易找到以 $\upsilon_i$ 为尾的弧，也容易找到以 $\upsilon_i$ 为头的弧，容易求得顶点的出度和入度，建立的时间复杂度与邻接表相同

5.对于邻接表中每一条边 $(\upsilon_i,\upsilon_j)$ 两个结点分别在第i个和第j个链表中的问题，邻接多重表在对边进行某种操作时更加方便，每一条边用一个结点表示，mark标志该边是否被搜索过，ivex和jvex表示该边依附的两个结点在图中的位置，ilink指向下一条依附ivex的边，jlink同理，info指向边相关信息，每一个顶点也用结点表示，data表示顶点相关信息，firstedge指示第一条依附于该点的边

6.无向图中邻接多重表与邻接表的区别仅仅在于同一条边在邻接表中用两个结点表示而在邻接多重表中只用一个结点

7.3 图的遍历

1.以邻接表作存储结构时，dfs遍历图的时间复杂度为 $O(n+e)$ .

7.4 图的连通性问题

1.两遍dfs算法求有向图强连通分量

2.Prim最小生成树：从当前点集相连的边中取权值最小的，把另一点并入点集，直到当前点集=顶点全集，时间复杂度 $O(n^2)$ .

3.割点：删去顶点 $\upsilon$ 以及和 $\upsilon$ 相关联的边之后图的一个连通分量分割成多个连通分量

4.没有割点的图称为重连通图，在连通图上至少删去k个顶点才能破坏图的连通性，称此图的连通度为k

5.割点的特性：①生成树的根有两棵或两棵以上的子树，则根结点必为割点②生成树中某非叶子结点 $\upsilon$ ，其某棵子树的根和子树中的其他结点均没有指向 $\upsilon$ 的祖先的回边，则 $\upsilon$ 为割点

6.tarjan算法求割点

7.5 有向无环图及其应用

1.如果从有向图某个顶点 $\upsilon$ 出发的遍历，在 $dfs(\upsilon)$ 结束之前出现一条从顶点 $u$ 到顶点 $\upsilon$ 的回边，则有向图中必定存在包含顶点 $u$ 和 $\upsilon$ 的环

2.拓扑排序时间复杂度 $O(n+e)$ .

3.关键路径是从开始点到完成点的最长路径的长度，时间复杂度 $O(n+e)$ .

7.6 最短路径

1.dijkstra每次选择的结点都是从未选择结点中选取距离源点最近的结点

这里稍微还有点东西没弄明白，先挖个坑吧（坑）

第8章动态存储管理

第9章查找

1.查找表是由同一类型的数据元素构成的集合，静态查找表只查询特定元素是否在表中和检索特定元素的属性，动态查找表在静态查找表的操作上加上插入和删除已存在的某个数据元素

2.关键字标识一个数据元素，主关键字唯一标识一个记录，次关键字识别若干记录的关键字

9.1 静态查找表

1.查找操作的性能分析通常比较平均查找长度，平均查找长度为和给定值进行比较的关键字个数的期望 $ASL=\sum\limits_{i=1}^nP_iC_i$ ，顺序查找 $ASL=\frac{n+1}{2}$ .

2.折半查找的性能分析通常画出查找过程的判定树，查找过程中和给定值进行比较的关键字个数至多为 $\lfloor log_2n\rfloor +1$ ，平均查找长度 $ASL_{bs}=log_2(n+1)-1$ .

3.斐波那契查找：根据斐波那契数列对表进行分割，平均性能比折半查找好，最坏性能比折半查找差（时间复杂度依然是 $O(nlogn)$ ）

4.插值查找：类似于二分查找，但是每次从自适应mid处开始查找，折半查找 $mid=\frac{low+high}{2}=low+\frac{1}{2}(high-low)$ ，插值查找是 $mid=low+\frac{key-a[low]}{a[high]-a[low]}(high-low)$ 。对于均匀分布的数据来说插值查找比二分查找快，但是不均匀分布的数据不一定比折半查找好

5.静态最优查找树（新内容，看了半天大体明白是什么意思了，但是核心要点为什么要这么做，这么做为什么是正确的还没有想清楚，挖个坑吧QAQ）

6.分块查找：分成b个块，每个块记录块控制区间内序列关键字的最大值，查找就可以通过先找到相应块（通常用二分查找），再暴力查找块内各个元素，时间复杂度 $O(\sqrt n)$ ，顺序查找确定所在块平均查找长度 $ASL_{bs}=L_s+L_w=\frac{1}{2}(\frac{n}{s}+s)+1$ ，二分查找确定所在块的平均查找长度 $ASL_{bs}\approx log_2(\frac{n}{s}+1)+\frac{s}{2}$ .

9.2 动态查找表

1.二叉排序树（BST）可以当作是不带平衡限制的平衡树，平衡树是BST的优化，满足左结点<根结点<右结点，查找和二分查找一样，删除结点时有两种方式：①左子树接到父结点上，右子树接到中序遍历被删除结点的前驱结点上②被删除结点的直接前驱顶替被删除结点，直接前驱的子树接到其父结点上。总之保持中序遍历始终不变的原则就是正确的

2.二叉排序树形态不唯一，平均查找长度 $P(n)\leq 2(1+\frac{1}{n})\ln n$ ，随机情况下平均查找长度和 $logn$ 是等数量级的，需要平衡化处理

3.平衡二叉树（AVL）左子树和右子树的深度之差的绝对值不超过1且左右子树都是平衡二叉树

4.平衡二叉树左旋右旋挖坑

5.平衡树查找性能分析：使用归纳法证明当 $h\geq 0$ 时， $N_h=F_{h+2}-1$ ，则 $N_h\approx \frac{\phi^{h+2}}{\sqrt 5-1}$ ，其中 $N_h$ 表示深度为h的平衡树中含有的最少结点数，因此平衡树上查找的时间复杂度为 $O(logn)$ .

动态查找表实在是看着头大，挖个坑先看下一节吧\捂脸

9.3 哈希表

1.对不同关键字可能得到同一哈希地址，称作冲突，具有相同函数值的关键字对该哈希函数来说是同义词

2.根据设定的哈希函数 $H(key)$ 和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表

3.构造哈希函数的方法：

①直接定址法：取关键字或关键字的某个线性函数值作为哈希地址 $H(key)=key$ 或 $H(key)=a\cdot key+b$ .

②数字分析法：假设关键字已知，取关键字的若干地址组成哈希地址

③平方取中法：取关键字平方后的中间几位为哈希地址

④折叠法：将关键字分割成位数相同的几部分，取这几部分的叠加和舍去进位作为哈希地址。叠加有移位叠加和间界叠加，移位叠加将分割后的每一部分最低位对齐叠加，相当于整数加法，间界叠加从一端到另一端沿分割界来回折叠，相当于第奇数个数正着取，偶数个数反着取然后做整数加法

⑤除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址，一般情况下可以选p为质数或不包含小于20的质因数的合数

⑥随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址

4.处理冲突的方法：

①开放定址法： $H_i=(H(key)+d_i) mod m$

（1） $d_i=1,2,3,\cdots,m-1$ ，称线性探测再散列

（2） $d_i=1^2,-1^2,2^2,-2^2,\cdots,\pm k^2(k\leq m/2)$ ，称二次探测再散列

（3）伪随机数序列，称伪随机探测再散列

②再哈希法：地址冲突时计算另一个哈希函数地址，不易发生聚集，但是增加了计算的时间

③链地址法：每个哈希地址设置一个线性链表

④建立公共溢出区：开设一个向量专门存放冲突的关键字

5.从线性探测再散列的过程中可以看到：当表中i，i+1，i+2位置上已填有记录时，下一个哈希地址为i、i+1、i+2和i+3的记录都将填入i+3的位置，在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象称作二次聚集

6.线性探测再散列在哈希表未填满的情况下总能找到一个不发生冲突的地址，二次探测再散列只有在哈希表长 $m=4j+3$ 的素数时才有可能，随机探测再散列取决于伪随机数列

7.哈希表的平均查找长度依赖于哈希表的装填因子 $\alpha$ ，计算方法为装填的记录数除以哈希表的长度

8.在查找成功情况下，线性探测再散列平均查找长度 $S_{nl}\approx \frac{1}{2}(1+\frac{1}{1-\alpha})$ ，随机探测再散列、二次探测再散列和再哈希的平均查找长度为 $S_{nr}\approx -\frac{1}{\alpha}ln(1-\alpha)$ ，链地址法平均查找长度为 $S_{nc}\approx 1+\frac{\alpha}{2}$

9.在查找不成功情况下，线性探测再散列平均查找长度 $U_{nl}\approx \frac{1}{2}(1+\frac{1}{(1-\alpha)^2})$ ，随机探测再散列、二次探测再散列和再哈希的平均查找长度为 $U_{nr}\approx \frac{1}{1-\alpha}$ ，链地址法平均查找长度为 $S_{nc}\approx \alpha+e^{-\alpha}$

第10章内部排序

10.1 概述

1.假设 $K_i=K_j$ ，K为关键字，且在排序前序列中 $R_i$ 领先于 $R_j$ ，若排序后 $R_i$ 仍领先于 $R_j$ ，则排序方法是稳定的，反之，若可能使排序后 $R_j$ 领先于 $R_i$ ，则排序方法是不稳定的

2.由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为内部排序和外部排序，内部排序指的是待排序记录存放在计算机随机存储器中进行的排序过程，外部排序指的是待排序记录的数量很大，内存一次不能容纳全部记录，在排序过程中需对外存进行访问的排序过程

3.内部排序大致分为插入排序、交换排序、选择排序、归并排序和计数排序五类

4.待排序记录序列有3中存储方式：①类似线性表的存储结构②存放在静态链表中，记录之间的次序关系由指针指示，实现排序不需要移动记录只需要修改指针，在此存储方式下实现的排序称链表排序③存在一段地址连续的存储单元中，附设地址向量指示记录存储位置，称地址排序

10.2 插入排序

1.直接插入排序：将一个记录插入到已排好序的有序表中，得到一个新的、记录数增1的有序表，最好情况待排序记录正序排列，此时关键字比较次数达到最小值n-1，记录不需移动，最坏情况待排序记录逆序排列，总比较次数达到最大值 $\frac{(n+2)(n-1)}{2}$ ，记录移动次数达到最大值 $\frac{(n+4)(n-1)}{2}$

2.平均情况直接插入排序关键字比较次数和移动记录次数约为 $\frac{n^2}{4}$ ，时间复杂度为 $O(n^2)$ .

3.折半插入排序：找关键字位置采用折半查找，仅减少了关键字的比较次数，记录的移动次数不变，时间复杂度仍为 $O(n^2)$ .

4.2-路插入排序：可以假设将存储空间看成环状的，则插入元素时可以分成以a[1]为首和以a[n]为尾的两部分，设置指针分别指向第一部分的尾部和第二部分的首部，当两个指针相遇时排序完成，减少了排序过程的移动记录的次数，但是需要n个记录的辅助空间，移动记录的次数为 $\frac{n^2}{8}$ ，时间复杂度为 $O(n^2)$ .

5.表插入排序与直接插入排序相比不同之处仅是以修改2n次指针代替移动记录，时间复杂度仍是 $O(n^2)$ .

6.希尔排序：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列记录“基本有序”时，再对全体记录进行一次直接插入排序，希尔排序的时间复杂度与增量序列有关，当增量序列 $dlta[k]=2^{t-k+1}-1$ 时，时间复杂度为 $O(n^{\frac{3}{2}})$ .

10.3 快速排序

1.起泡排序：每趟排序将最大的关键字排到最后，时间复杂度为 $O(n^2)$ .

2.快速排序是对起泡排序的改进，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，分别对两个序列继续进行排序。每次设置一个基准值，设置头尾指针，分别找第一个比基准值大的值和第一个比基准值小的值，如果头指针<尾指针则进行交换，直到头指针>=尾指针，这时基准值左半部分就是小于它的，右半部分就是大于它的，然后采用分治的思想直到所有序列都排了一遍

3.快速排序的平均时间为 $T_{avg}(n)=kn\ln n$ ，k为某个常数，经验证明，所有同数量级的排序方法中，快速排序的常数因子k最小

4.快速排序被认为是在所有同数量级的排序方法中平均性能最好，但是若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，时间复杂度为 $O(n^2)$ ，快速排序需一个栈空间来实现递归，栈的最大深度为 $\lfloor log_2n\rfloor +1$

10.4 选择排序

1.简单选择排序：通过n-i次关键字比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换，所需进行记录移动的操作次数最小值为0，最大值为 $3(n-1)$ ，无论记录的初始排列如何，所需关键字比较次数相同，均为 $\frac{n(n-1)}{2}$ ，总时间复杂度为 $O(n^2)$ .

2.树形选择排序：在序列的基础上建立完全二叉树，每个结点控制其子树的最小值，然后每次取根结点的值即为最小值，取完后在 $O(logn)$ 的复杂度找到该叶子结点，修改为无穷大然后继续找次小值，基本上等同于线段树的求最值和单点修改的操作，时间复杂度 $O(nlogn)$ .

3.堆排序：为序列建立堆，每次取堆的根结点，然后按照堆的性质调整堆的结构，时间复杂度为 $O(nlogn)$ ，仅需一个记录大小供交换用的辅助存储空间

10.5 归并排序

1.2-路归并排序：通过将两个有序线性表合并为一个有序线性表的思路启发，2-路归并排序一开始将长度1的各个数当作有序子序列进行合并，合并长度为2的序列之后继续合并，直到合并成长度为n的有序序列，是稳定的 $O(nlogn)$ 排序算法，需要和待排序列等量的存储空间

10.6 基数排序

1.链式基数排序：借助“分配”和“收集”两种操作对单逻辑关键字进行排序，逻辑关键字可以看作由若干个关键字复合而成，如三位数排序可以看作由个位数、十位数和百位数三个关键字复合而成，用静态链表存储n个待排记录，按照个位数、十位数和百位数进行“分配”后“收集”就完成了排序，假设每个记录含有d个关键字，每个关键字的取值范围为rd个值，链式基数排序的时间复杂度为 $O(d(n+rd))$ ，辅助空间为2rd个队列指针，链式存储比顺序存储还增加了n个指针域的空间

10.7 各种内部排序方法的比较讨论

1.排序方法平均时间最坏情况辅助存储

简单排序 $O(n^2)$ $O(n^2)$ $O(1)$

快速排序 $O(nlogn)$ $O(n^2)$ $O(logn)$

堆排序 $O(nlogn)$ $O(nlogn)$ $O(1)$

归并排序 $O(nlogn)$ $O(nlogn)$ $O(n)$

基数排序 $O(d(n+rd))$ $O(d(n+rd))$ $O(rd)$

2.n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多

3.当序列中的记录“基本有序”或n值较小时，直接插入排序是最佳的排序方法

4.基数排序的时间复杂度也可写成 $O(d\cdot n)$ ，是稳定的内排方法，所有时间复杂度为 $O(n^2)$ 的简单排序法也是稳定的，快速排序、堆排序和希尔排序等都是不稳定的

5.本章排序方法除基数排序之外都是基于关键字比较这个操作进行的，均可用判定树来描述过程，从根结点到叶子结点的一条路径长度代表了一次排列所进行的比较次数，描述n个记录排序的判定树上必定存在一条长度为 $\lceil log_2(n!)\rceil$ 的路径，而实际上一般的排序方法都大于这个理论值。根据斯特林公式， $\lceil log_2(n!)\rceil=O(nlogn)$ ，借助于“比较”进行排序的算法在最坏情况下能达到的最好的时间复杂度为 $O(nlogn)$ .

第1章 绪论