啃《数据结构-C语言版》，目的是弄明白各种笔试中干瞪眼的题目。

一、绪论

1.数据(data)：对客观事物的符号表示，在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。

2.数据元素 (data element)：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

3.数据对象(data object)：性质相同的数据元素的集合，是数据的一个子集。

4.数据结构(data structure)：相互存在一种或多种特定关系的数据元素的集合。

5.数据之间的四类基本结构：集合、线性结构、树形结构、网状结构。

6.计算机中表示信息的最小单位是二进制的一位，称为位。若干位组合形成一个位串可以用来表示一个数据元素，称这个位串是元素/节点。一个数据元素可能由若干数据项组成，则表示每个数据项的子串称为数据域。元素/节点是数据元素在计算机中的映像。

（<数据元素 name="元素/节点"><数据项1>位位位<//数据项1><数据项2>位位位位位位位位<//数据项2><//数据元素>）

7.数据元素之间关系为逻辑结构->映射到计算机中表示数据的物理结构/存储结构。元素之间的关系在计算机中分为两种表示方法：顺序映像和非顺序映像->两种不同的存储结构：顺序存储结构和链式存储结构。

8.数据类型是一个值的集合和定义在这个集合上的一切操作的总称(原子类型、结构类型)。抽象数据类型是一个数学模型以及定义在这个模型上的一切操作(原子类型、固定聚合类型、可变聚合类型，后两者也可统称为结构类型)。

9.算法是对特定问题求解步骤的一种描述，是指令的有限序列，每一条指令表示一个或多个操作。有以下5个重要特性

• 有穷性 一个算法必须总是对任何合法的输入值执行有穷步之后结束，并且每一步都要在有穷时间内完成。
• 确定性 算法中美一条指令必须有明确的含义，并且在任何条件下，算法只有唯一的一条执行路径(对相同的输入只能得出相同的输出)。
• 可行性 一个算法是能行的，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
• 输入 一个算法有零个或多个输入，取自某个特定的对象集合。
• 输出 一个算法有一个或多个输出，输出是同输入有某些特定关系的量。

10.算法设计应考虑以下目标：正确性、可读性、健壮性、效率与低存储量需求。

11.时间复杂度： 时间复杂度是指执行算法所需要的计算工作量

• 先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))

---

二、线性表

1.线性结构特点：

• 存在唯一一个被称为“第一个”的数据元素
• 存在唯一一个被称为“最后一个”的数据元素
• 除了第一个数据元素外，每个数据元素都只有一个前趋
• 除了最后一个数据元素外，每个数据元素都只有一个后继

2.一个线性表是n个数据元素的有限序列。复杂的线性表中，一个数据元素由若干个数据项组成，则数据元素称为记录，含有大量记录的线性表称为文件。

3.线性链表：含有存储元素信息的数据域和存储直接后继存储位置的指针域，也叫单链表。链表的存取从头指针开始，最后一个结点的指针为NULL。

4.与指针描述的线性链表不同，数组描述的链表称为静态链表。

5.循环链表是另一种形式的链式存储结构，特点是表中最后一个节点的指针域指向头结点，链表形成一个环，从任意结点出发都能找到表中其它结点。(单链的循环链表和多重链的循环链表)

6.双向链表有两个指针域，一个指向直接后继，一个指向直接前趋。双向链表的循环表有两个方向。

---

三、栈和队列

1.从数据结构角度看，栈和队列也是线性表，栈和队列的基本操作是线性表操作的子集，称为限定性的数据结构。

2.栈是限定仅在表尾进行插入或删除操作的线性表，表尾称为栈顶，表头称为栈底。栈称为后进先出(LIFO)的线性表。

3.栈和线性表类似，也有两种存储表示方法(顺序栈和链栈)。

4.栈的应用：数制转换、括号匹配检验、行编辑程序、迷宫求解、表达式求解……

5.当一个函数运行期间调用另一个函数时，在运行被调用函数之前，系统需要完成3件事：

• 将所有的实在参数、返回地址等信息传递给被调用函数保存；
• 为被调用函数的局部变量分配存储区；
• 将控制转移到北调函数的入口；

6.从被调用函数返回到调用函数之前，系统也应完成3件工作：

• 保存被调用函数的计算结果；
• 释放被调用函数的数据区；
• 按照被调函数保存的返回地址讲控制转移到调用函数；

7.与栈相反，队列是一种先进先出(FIFO)的线性表，只允许在表的一端进行插入(队尾)，另一端删除元素(队头)。

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

• 两个栈底相邻接的栈(限定某个端点插入的数据只能从该端点删除)；
• 一个端点允许插入和删除而另一个端点只允许删除(输出受限)；
• 一个端点允许插入和删除而另一个端点只允许插入(输入受限)；

---

4.串

1.串(或字符串)是由另个或多个字符组成的有限序列。串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。

2.串有定长顺序存储表示(用一组地址连续的存储单元存储串值的字符序列)、堆分配存储表示(一组地址连续的存储单元存放串值字符序列，但存储空间是程序执行过程中动态分配而得的)、块链存储表示。

---

5.数组和广义表

1.二维数组有两种存储方式：

• 以列序为主序的存储方式(C)；
• 以行序为主序的存储方式(FORTRAN)；

2.压缩存储：一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或令元素，为多个值相同的元值分配一个存储空间，对零元不分配空间。

3.广义表可以包含单个元素，也可以包含广义表(称为子表)。 第一个元素为表头，其与元素组成的表为表尾。

4.广义表的表结点由3个域组成：标志域、指示表头的指针、指示表尾的指针域。原子结点只有两个域：标志域和值域。

5.广义表存储结构中的几种情况：

• 除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点，且该结点中的hp域指示列表表头(原子结点/表结点)，tp域指向列表表位(除空表尾，必为表结点)。
• 容易分清列表中原子和子表所在的层次。
• 最高层的表结点个数为列表的长度。

6.广义表的深度定义为广义表中括弧的重数，是广义表的一种量度。空表的深度为1。

---

6.树和二叉树

1.树是n个结点的有限集。在任意一棵非空树中：

• 有且仅有一个特定的称为根(Root)的结点；
• 当n>1时，其余结点可分为m(m>0)个互不相交的有限集，其中每一个集合本身又是一棵树，称为根的子树；

2.树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)，度为0的结点称为叶子(Leaf)或终端结点，度不为0的结点称为非终端结点或分支结点。

3.树的度是树内各结点的度的最大值。

4.树中结点的最大层次称为树的深度或高度。

5.如果将树中结点的各子树看成从左到右是有次序的(不能互换)，则称该树为有序树，否则称为无序树。

6.森林(Forest)是m(m>=0)棵互不相交树的集合。

7.二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，次序不能颠倒。

8.二叉树的性质：

• 性质1：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)；
• 性质2：深度为k的二叉树至多有2^k-1个结点(k>=1)；
• 性质3：对任何一棵二叉树，如果其终端结点数为n，度为2的结点数为m，则n=m+1；
• 性质4：具有n个结点的完全二叉树的深度为[log2(n)+1]；
• 性质5：对一棵有n个结点的完全二叉树，结点按层序排号，对任意结点i(1<=i<=n)，有 (1)如果i=1，则结点i是二叉树的根，无双亲；若i>1，则其双亲是结点[i/2]。(2)若果2i>n，则结点i无左孩子，否则其左孩子是结点2i。(3)如果2i+1>n，则结点i无右孩子，否则右孩子是结点2i+1。

9.一棵深度为k且有2^k-1个结点的二叉树称为满二叉树，特点是每一层上的结点数都是最大结点数。

10.至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，称为完全二叉树。

11.满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。

12.二叉树的存储结构

• 顺序存储结构：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，将完全二叉树上编号为i的阶段元素存储在如上定义的一维数组中下标为i-1的分量中，0来表示不存在此结点；
• 链式存储结构：二叉树的链表中的结点至少包含3个域：数据域和左右指针域，有时为了方便找结点的双亲还加入了指向双亲结点的指针域，分别称为二叉链表和三叉链表；

13.先序遍历、中序遍历和后序遍历二叉树

(1)先序遍历二叉树：

• 访问根结点
• 先序遍历左子树
• 先序遍历右子树

(2)中序遍历二叉树：

• 中序遍历左子树
• 访问根结点
• 中序遍历右子树

(3)后序遍历二叉树：

• 后序遍历左子树
• 后序遍历右子树
• 访问根节点

如图所示：

• 先序遍历 - + a * b - c d / e f
• 中序遍历 a + b * c - d - e / f
• 后序遍历 a b c d - * + e f / -

14.以结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

15.树的存储结构

(1)双亲表示法：利用了除根结点以外，每个结点只有唯一双亲的性质。但这种表示法中求结点的孩子时需要遍历整个结构。

(2)孩子表示法：利用树中每个结点可能有多棵子树，可用多重链表，即每个结点有多个指针域，每个指针指向一棵子树的根结点。与双亲表示法相反，孩子表示法便于设计孩子操作的实现，而两者的结合就能够融合它们各自的优点。

(3)孩子兄弟表示法：又称二叉树表示法或二叉链表表示法。以二叉链表作树的存储结构，链表中两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。

16.森林与二叉树的转换：树的二叉链表表示定义可知，任何一棵和树对应的二叉树，其右子树必空。(因为根结点无兄弟结点)，因此可导出森林和二叉树的对应关系。

17.有两种次序遍历树的方法：一种是先根次序遍历树(先访问根结点，然后一次先根遍历根的每棵子树，ABCDE)，另一种是后根次序遍历(先依次后根遍历每棵子树，然后访问根结点，BDCEA)。

18.按照森林和树相互递归的定义，森林的两种遍历方法：

(1)先序遍历森林(ABCDEFGHIJ)

• 访问森林中第一棵树的根结点；
• 先序遍历第一棵树中根结点的子树森林；
• 先序遍历除去第一棵树之后剩余的树构成的森林；

(2)中序遍历森林(BCDAFEHJIG)

• 中序遍历森林中第一棵树的根结点的子树森林；
• 访问第一棵树的根节点；
• 中序遍历除去第一棵树之后剩余的树构成的森林；

19.如果集合S中的关系R是自反的、对称的和传递的，则称它为一个等价关系。

20.若R是集合S的等价关系，则由这个等价关系可产生这个集合的唯一划分。划分为若干不相交子集，它们的并即为S，则这些子集称为S的R等价类。

21.路径上的分支树木称为路径长度，树的路径长度是从树根到每一结点的路径长度之和。

22.结点的带权路径长度为从该结点到树根结点的路径长度与结点上权的乘积。树的带权路径长度为树种所有叶子结点的带权路径长度之和。带权路径长度WPL最小的二叉树称作最优二叉树或霍夫曼树。

23.构造霍夫曼树：

• 根据给定的n个权值构成n棵二叉树集合F，起哄每棵二叉树T中只有一个带全为w的根结点，其左右子树均为空。
• 在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新二叉树，且置新的二叉树的根节点的权值为其左右子树上根结点的权值之和。
• 在F中删除这两棵树，同事将新的到的二叉树加入F中。
• 重复以上两步，直到F中只含一棵树为止，它便是霍夫曼树。

24.二叉树相似指二者都为空树或者二者均不为空树，且它们的左右子树分别相似。二叉树等价指二者不仅相似，而且它们所有对应结点上的数据元素均相同。

---

7.图

1.在图中的数据元素通常称为顶点。图分为有向图和无向图。

2.顶点的度是和顶点相关联的边的数目。在有向图中，以v顶点为尾的弧的数目称为v出度，以v为头的弧的数目称为v的入度。

3.路径的长度是路径上的边或弧的数目，第一个顶点和最后一个顶点相同的路径称为回路或环。序列中定点不重复出现的路径称为简单路径。

4.在无向图中，如果两个顶点之间有路径，则称两个顶点是连通的。如果对于图中任意两个顶点都是连通的，则称为连通图。连通分量指的是无向图中的极大连通子图。

5.在有向图中，如果对于每一对顶点都存在路径，则称是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

6.一个连通图的生成树是一个极小连通子图，他含有图中全部顶点，但只有最构成一棵树的n-1条边。

• 一棵有n个顶点的生成树有且仅有n-1条边；
• 如果一个图有n个顶点和小于n-1条边，则是非连通图；
• 如果它多于n-1条边，则一定有环。

7.(图的数组表示法)图的邻接矩阵，顶点之间若存在路径(有向图有方向性)，则矩阵相应点为1，否则为0，顶点的度是邻接矩阵第i行或j列元素之和。

8.无向图的邻接矩阵具有对称性，所以在有向图中，矩阵的行元素之和为出度，列元素之和为入度。

9.邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的边(有向图表示以顶点vi为尾的弧)。

10.十字链表是有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。

11.邻接多重表是无向图的另一种链式存储结构，由6个域组成。

12.深度优先搜索：从某顶点出发，访问此顶点，并依次从此顶点的未被访问的临接点出发深度优先遍历图，知道所有的和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程直到图中所有顶点都被访问到。

13.广度优先搜索：类似树的按层次遍历的过程，从顶点出发，访问此顶点后依次访问其各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点(先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点)，直至图中所有已被访问的顶点的邻接点都被访问到。

14.最小生成树，就是构造连通网的最小代价生成树，生成树的代价就是树上各边的代价之和。有Prim算法和Kruskal算法。

15.删除一个顶点及相关联的各边后，可以将图的一个连通分量分割成两个或两个以上的连通分量，就称这个顶点为关节点。一个没有关节点的连通图称为重连通图。若至少删去k个顶点才能破坏图的连通性，称图的连通度为k。

---

8.动态存储管理

1.三种分配策略：首次拟合法、最佳拟合法、最差拟合法。

---

9.查找

1.二叉排序树：或者是空树，或者具有以下性质

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 它的左右子树也分别是二叉排序树；

2.平衡二叉树：或者是空树，或者具有以下性质

• 它的左右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1；(若将二叉树上结点的平衡因子定义为该结点的左子树的深度减去它右子树的深度，则平衡二叉树上所有节点的平衡因子只可能是-1、0、1)；

3.在平衡二叉排序树上插入一个新的数据元素e的递归算法描述：

• 若BBST(平衡二叉树)为空树，则插入一个数据元素为e的新结点作为BBST的根节点，树的深度增1；
• 若e的关键字和BBST的根结点的关键字相等，则不进行插入；

• 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加+1时，分别就以下情况处理之：

  ①BBST的根结点的平衡因子为-1(右子树的深度大于左子树的深度)：则将根结点的平衡因子更改为0，BBST的深度不变。

  ②BBST的根结点的平衡因子为0(左右子树的深度相同)：则将根节点的平衡因子更改为1，BBST的深度增1。

  ③BBST的根结点的平衡因子为1(左子树的深度大于右子树的深度)：

  ->若BBST的左子树根节点的平衡因子为1，则续进行单向右旋平衡处理，并且在右旋处理之后，将根结点和右子树根结点的平衡因子更改为0，树的深度不变。 ->若BBST的左子树根结点的平衡因子为-1，则需进行先向左后向右的双向旋转平衡处理，并且在旋转处理之后，修改根节点和左右子树根结点的平衡因子，树的深度不变。

• 若e的关键字大于BBST的根结点的关键字，并且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加+1时，分别和上述处理操作对称处理之。

4.B-树是一种平衡的多路查找树，在文件系统中很有用，一颗m阶B-树，或为空树，或者满足下列特性的m叉树：

• 树中每个结点至多有m棵子树；
• 若根节点不是叶子结点，则至少有两棵子树；
• 除根之外的所有非终端结点至少有的[m/2]棵子树；
• 所有的非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)。其中Ki是关键字，ki<ki+1，Ai是指向子树跟结点的指针，且Ai-1所指子树中所有结点的关键字均小于ki，An所指子树中所有结点的关键字均大于Kn，n为关键字个数；
• 所有的叶子结点都出现在同一层次上，并且不带信息；

5.B+树是应文件系统所需而出的一种B-树的变型树，m阶B+树和m阶B-树差异在于：

• 有n棵子树的结点中含有n个关键字；
• 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序连接；
• 所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大或最小关键字；

6.更多关于B+、B-、B、B*树的联系特点见这篇文章。

7.根据设定的哈希函数和处理冲突的方法将一组关键字影像到一个有限的连续的地址集(区间)上，并以关键字在地址集中的”像”作为记录在表中的存储位置，称为哈希表，映像过程称为哈希造表或者散列，所得的存储位置称为哈希地址或散列地址。

8.若对于关键字集合中的任一关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀地哈希函数。就是是关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

9.常用的构造哈希函数的方法：

• 直接定址法：取关键字或关键字的某个线性函数值为哈希地址；
• 数字分析法：假设关键字是以r为基的数（如果10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址；
• 平方取中法：取关键字的平方后的中间几位为哈希地址；
• 折叠法：将关键字分割成位数相同的几部分（最后一部分位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址；
• 除留余数法：取关键字被某个不大于哈希表表长m的树p除后所得余数为哈希地址；
• 随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址，当关键字长度不等时采用此法构造哈希函数比较恰当；

10.实际工作中构造不同的哈希函数需要考虑的因素有：

• 计算海西函数所需时间；
• 关键字的长度；
• 哈希表的大小；
• 关键字的分布情况；
• 记录的查找频率；

11.处理冲突的方法：

• 开放定址法：线性探测再散列、二次探测再散列、伪随机探测再散列，易产生聚集；
• 再哈希法：不易产生聚集，但增加了计算的时间；
• 链地址法：将所有关键字为同义词的记录存储在同一线性链表中；
• 建立公共溢出区：所有关键字和基本表中关键字为同义词的记录，不管由哈希函数的到的哈希地址是什么，一旦发生成图，都填入溢出表；

12.哈希表的查找，给定K值，根据造表时设定的哈希函数求哈希地址，若表中此位置没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找下一地址，知道哈希表中某个位置为空或者表中所填记录关键字等于给定值为止。

13.从哈希表的查找过程中可见：

• 虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于冲突的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程，因此仍需要以平均查找长度作为衡量哈希表的查找效率的量度；
• 查找过程中需和给定值进行比较的关键字的个数取决于下列三个元素：哈希函数，处理冲突的方法和哈希表的装填因子；

14.哈希表的装填因子定义为：α = 表中填入的记录数 / 哈希表的长度。

---

10.内部排序

1.内部排序：待排序记录存放在计算机随机存储器中进行的排序过程。外部排序：带排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

2.直接插入排序：将一个记录插入倒已排好序的有序表中，从而得到一个新的、记录数增1的有序表，其时间复杂度为O(n2)。

3.折半插入排序：所需附加存储空间和直接插入排序相同，减少了关键字间的比较次数，但记录的移动次数不变，因此其时间复杂度仍为O(n2)。

4.2-路插入排序：在折半插入排序的基础上改进，目的是减少排序过程中移动记录的次数，但是为此需要n个记录的辅助空间。

5.表插入排序：表结构就是一个静态链表，它可以用一个数组来初始化，初始化用头元素和第一个元素组成一个循环链表，然后排序时从第二个元素开始插入到这个循环链表中，当然只是修改每个元素的next域。使头结点的next域始终指示最小的那个元素，然后依次向下：每一个元素的next域都指示比它稍大的那个元素。最大的元素的next域指示头结点。这样形成一个循环链表。

6.希尔排序：又称缩小增量排序，基本思想是将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序“时，再对全体记录进行一次直接插入排序。

7.快速排序：是对起泡排序的一种改进，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

8.一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为key，首先从high所指的位置向前搜索找到第一个关键字小于key的记录和枢轴记录交换，然后从low所值位置其向后搜索，找到第一个关键字大于key的记录和枢轴记录交换，重复这两步知道low = high为止。

9.快速排序是目前被认为是最好的一种内部排序方法，在所有同数量及的排序方法中，其平均性能最好。

10.选择排序：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。

11.树形选择排序：首先对n个记录的关键字进行两两比较，然后再其中n/2个较小者之间再进行两两比较，重复直到选出最小关键字的记录为止。

12.堆排序：若将序列对应的一维数组看成是一个完全二叉树，那堆的含义表明，完全二叉树中所有非终端结点的值俊不大于或不小于其左右孩子结点的值。

13.归并排序：将待排序序列R[0…n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列，关于归并排序的详细信息见这篇文章.

14.

排序法	平均时间	最差情况	稳定度	额外空间	备注
冒泡	O(n2)	O(n2)	稳定	O(1)	n小时较好
交换	O(n2)	O(n2)	不稳定	O(1)	n小时较好
选择	O(n2)	O(n2)	不稳定	O(1)	n小时较好
插入	O(n2)	O(n2)	稳定	O(1)	大部分已排序时较好
基数	O(d(n+rd))	O(d(n+rd))	稳定	O(n)
快速	O(nlogn)	O(n2)	不稳定	O(1)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(nlogn)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好

---

11.外部排序

1.外部排序，待排序的记录存储在外储存器上，在排序过程中续进行多次的内、外存之间的交换。

2.先将大文件的原始序列分割成适合内存的几部分，然后依次读入内存中进行内部排序（比如快排），排序完成后分别再保存回外存。接下来按照外存保存的文件个数划分内存为n+1，其中n份为读入buffer，其余1份为输出buffer，然后做n路归并排序。

---

12.文件

1.文件是由大量性质相同的记录组合成的集合。可以按照记录的类型不同分成操作系统文件和数据库文件两类。

• 操作系统文件：仅是一维的连续字符序列，无结构、无解释；
• 数据库文件：带有结构的记录的集合；

2.顺序文件是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。它的特点是：

• 存取第i个记录，必须西安搜索在它之前的i-1个记录；
• 插入新的记录时只能加在文件的末尾；
• 若要更新文件中的某个记录，则必须将整个文件进行复制；