【软考数据库】第三章 数据结构与算法

目录

3.1 数据结构
        3.1.1 线性结构
        3.1.2 数组
        3.1.3 矩阵
        3.1.4 树与二叉树
        3.1.5 图

3.2 查找
        3.2.1 顺序查找
        3.2.2 折半查找
        3.2.3 哈希表

3.3 排序
        3.3.1 直接插入排序
        3.3.2 希尔排序
        3.3.3 简单选择排序
        3.3.4 堆排序
        3.3.5 冒泡排序
        3.3.6 快速排序
        3.3.7 归并排序
        3.3.8 基数排序
        3.3.9 内部排序算法总结
        3.3.10 算法特性

前言：

笔记来自《文老师软考数据库》教材精讲，精讲视频在b站，某宝都可以找到，个人感觉通俗易懂。

3.1 数据结构

3.1.1 线性结构

• 线性结构：每个元素最多只有一个出度和一个入度，表现为一条线状。线性表按存储方式分为顺序表和链表。
• 存储结构：
  • 顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻。
  • 链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。

顺序存储和链式存储的对比如下图所示 

（1）在空间方面：因为链表还需要存储指针，因此有空间浪费存在。
（2）在时间方面，当需要对元素进行破坏性操作 (插入、删除) 时，链表效率更高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他节点位置都需要变动。
（3）而当需要对元素进行不改变结构操作时(读取、查找)，顺序表效率更高因为其物理地址是连续的，如同数组一般只需按索引号就可快速定位，而链表需要从头节点开始，一个个的查找下去。

• 栈和队列队列、栈结构如下图，队列是先进先出，分队头和队尾栈是先进后出，只有栈顶能进出。
• 循环队列
  设循环队列Q的容量为MAXSIZE，初始时队列为空，且Qrear和Qfront都等于0；元素入队时修改队尾指针，即令Qrear=(Q.rear+1)%MAXSIZE；元素出队时修改队头指针，即令Qfront==(Qfront+1)%MAXSIZE
• 根据队列操作的定义，当出队操作导致队列变为空时，有Qrear==Qfront;若入队操作导致队列满，则Qrear==Qfront。
• 在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的，此时仅仅根据Qrear和Qfront 之间的关系无法断定队列的状态。为了区别队空和队满的情况，可采用以下两种处理方式:其一是设置一个标志，以区别头、尾指针的值相同时队列是空还是满;其二是牺牲一个存储单元，约定以“队列的尾指针所指位置的下一个位置是队头指针时”表示队列满。
• 字符串是一种特殊的线性表，其数据元素都为字符。
  • 空串：长度为0的字符串，没有任何字符。
  • 空格串：由一个或多个空格组成的串，空格是空白字符，占一个字符长度。
  • 子串:串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串，空串是任意串的子串。
  • 串的模式匹配:子串的定位操作，用于查找子串在主串中第一次出现的位置的算法。

【模式匹配算法】

• 朴素的模式匹配算法：也称为布鲁特一福斯算法，其基本思想是从主串的第1个字符起与模式串的第1个字符比较，若相等，则继续逐个字符进行后续的比较否则从主串中的第2个字符起与模式串的第1个字符重新比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成功，否则称为匹配失败。 

3.1.2 数组

• 数组是定长线性表在维度上的扩展，即线性表中的元素又是一个线性表。N维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。
• 其可以表示为行向量形式或者列向量形式线性表，单个关系最多只有一个前驱和一个后继，本质还是线性的。
• 数组结构的特点：数据元素数目固定，数据元素类型相同;数据元素的下标关系具有上下界的约束且下标有序数
• 组数据元素固定，一般不做插入和删除运算，适合于采用顺序结构
• 数组存储地址的计算，特别是二维数组，要注意理解，假设每个数组元素占用存储长度为len，起始地址为a，存储地址计算如下(默认从0开始编号)

3.1.3 矩阵

• 特殊矩阵:矩阵中的元素(或非0元素)的分布有定的规律。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵
• 稀疏矩阵:在一个矩阵中，若非零元素的个数远远少于零元素个数，且非零元素的分布没有规律。
• 存储方式为三元组结构，即存储每个非零元素的(行列，值)。

3.1.4 树与二叉树

• 树是n个节点的有限集合(n>=0)当n=0时称为空树，在任一颗非空树中，有且仅有-个根节点。其余结点可分为m(m20)个互不相交的有限子集T1，T2，Tm，其中，每个Ti...又都是一棵树，并且称为根结点的子树。
• 树的基本概念如下：
  （1）双亲、孩子和兄弟。结点的子树的根称为该结点的孩子，相应地，该结点称为其子结点的双亲。。具有相同双亲的结点互为兄弟。
  （2）结点的度。一个结点的子树的个数记为该结点的度。例如A的度为3，B的度为2，C的度为0，D的度为1。
  （3）叶子结点。叶子结点也称为终端结点，指度为0的结点。例如，E、F、c、G都是叶子结点
  （4）内部结点。度不为0的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。例如，B、D都是内部结点。
  （5）结点的层次。根为第一层，根的孩子为第二层，依此类推，若某结点在第i层，则其孩子结点在第i+1层。例如，A在第1层，B、C、D在第2层，E、F和G在第3 层。
  （6）树的高度。一棵树的最大层数记为树的高度(或深度)。例如，图中所示树的高度为3
  （7）有序(无序)树。若将树中结点的各子树看成是从左到右具有次序的，即不能交换则称该树为有序树，否则称为无序树。

• 二叉树是n个节点的有限集合，它或者是空树或者是由一个根节点及两颗互不相交的且分别称为左有子村的一又村村所组成。

• 二叉树有一些性质如下，要求掌握，在实际考试中可以用特殊值法验证。
  （1）二叉树第i层 (i>=1) 上至多有2^(i-1)个节点。
  （2）深度为k的二叉树至多有2^k - 1个节点(k>=1)
  （3）对任何一棵二叉树，若其终端节点数为n0，度为2 的节点数为n2，则n0=n2 + 1。
  此公式可以画一个简单的二叉树使用特殊值法快速验证，也可以证明如下设一棵二叉树上叶结点数为no，单分支结点数为n,，双分支结点数为n，则总结点数=n,+ni+n2。在一棵二叉树中，所有结点的分支数(即度数)应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n,+2n。由于二叉树中除根结点以外每个结点都有唯一的一个分支指向它，因此二叉树中:总的分支数=总结点数-1。
  （4）具有n 个节点的完全二叉树的深度为|log2 nl+ 1 
• 二叉树的顺序存储结构：
  顺序存储，就是用一组连续的存储单元存储二叉树中的节点，按照从上到下从左到右的顺序依次存储每个节点。
• 对于深度为k的完全二叉树，除第k层外，其余每层中节点数都是上一层的两倍，由此，从一个节点的编号可推知其双亲、左孩子、右孩子结点的编号。假设有编号为的节点，则有：
  （1）若i=1，则该节点为根节点，无双亲;
  （2）若i>1，则该节点的双亲节点为i/2。
  （3）若2i<=n，则该节点的左孩子编号为2i，否则无左孩子。
  （4）若2i + 1<=n，则该节点的右孩子编号为2i+1，否则无右孩子
• 显然，顺序存储结构对完全二叉树而言既简单又节省空间，而对于一般二叉树则不适用。因为在顺序存储结构中，以节点在存储单元中的位置来表示节点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储也就是要添上一些实际并不存在的“虚节点”，这将造成空间的浪费。
• 二叉树的链式存储结构：
  由于二叉树中节点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用三叉链表或二叉链表(即一个节点含有三个指针或两个指针)来存储二叉树，链表的头指针指向二叉树的根节点
• 一颗非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分也就遍历了整颗二叉树。这三部分遍历的基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有下列三种遍历方式：
  先序 (前序) 遍历: 根左右
  中序遍历: 左根右
  后序遍历: 左右根
  示例:前序:12457836 中序: 42785136 后序:48752631

• 层次遍历:按层次，从上到下，从左到右
• 反向构造二叉树
  仅仅有前序和后序是无法构造二叉树的，必须要是和中序遍历的集合才能反向构造出二叉树。
  构造时，前序和后序遍历可以确定根节点，中序遍历用来确定根节点的左子树节点和右子树节点，而后按此方法进行递归，直至得出结果。
• 引入线索二叉树是为了保存二叉树遍历时某节点的前驱节点和后继节点的信息，二叉树的链式存储只能获取到某节点的左孩子和右孩子结点，无法获取其遍历时的前驱和后继节点，因此可以在链式存储中再增加两个指针域，使其分别指向前驱和后继节点，但这样太浪费存储空间，考虑下述实现方法：
  （1）若n个节点的二叉树使用二叉链表存储，则必然有n+1个空指针域，利用这些空指针域来存放节点的前驱和后继节点信息，为此，需要增加两个标志，以区分指针域存放的到底是孩子结点还是遍历节点，如下：

  

  （2）若二又树的二叉链表采用上述结构，则称为线索链表，其中指向前驱、后继节点的指针称为线索，加上线索的二叉树称为线索二叉树。

• 最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树，相关概念如下路径：
  • 树中一个结点到另一个结点之间的通路
  • 结点的路径长度：路径上的分支数目。
  • 树的路径长度：根节点到达每一个叶子节点之间的路径长度之和。
  • 权：节点代表的值结点的。
  • 带权路径长度：该结点到根结点之间的路径长度乘以该节点的权值
  • 树的带权路径长度(树的代价)：树的所有叶子节点的带权路径长度之和
• 哈夫曼树的求法: 给出一组权值，将其中两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到该组权值中。重复进行上述步骤，直至所有权值都被使用完。
• 若需要构造哈夫曼编码 (要保证左节点值小于右节点的值，才是标准的哈夫曼树)，将标准哈夫曼树的左分支设为0，右分支设为1，写出每个叶节点的编会发现，哈夫曼编码前缀不同，因此不会混淆，同时也是最优编码。
• 查找二叉树上的每个节点都存储一个值，且每个节点的所有左孩子结点值都小于交节点值，而所有右孩子结点值都大于父节点值，是一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作。
• 二叉排序树的查找效率取决于二叉排序树的深度，对于结点个数相同的二叉排序树，平衡二叉树的深度最小，而单枝树的深度是最大的，故效率最差
• 平衡二叉树又称为AVL 树，它或者是一棵空树，或者是具有下列性质的二又树它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。若将二叉树结点的平衡因子 (Balance Factor，BF) 定义为该结点左子树的高度减去其右子树的高度，则平衡二叉树上所有结点的平衡因子只可能是-10和1。只要树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

3.1.5 图

• 无向图：图的结点之间连接线是没有箭头的，不分方向。
• 有向图：图的结点之间连接线是箭头，区分A到B，和B到A是两条线。
• 完全图：无向完全图中，节点两两之间都有连线，n个结点的连线数为(n-1)+(n-2)+...+1= n*(n-1)/2；有完全图5b节点两两之间都有互通的两个箭头，个节点的连线数为n*(n-1)。
• 度、出度和入度：顶点的度是关联与该顶点的边的数目。在有向图中，顶点的度为出度和入度之和。
• 路径：存在一条通路，可以从一个顶点到达另一个顶点。
• 子图：有两个图G=(V, E)和G'=(V',E)，如果 C VE'C E，则称G为G的子图。
• 连通图和连通分量：针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。无向图G的极大连通子图称为其连通分量。强连通图和强连通分量:针对有向图。若有向图任意两个顶点间都互相存在路径，即存在v到u，也存在u到v的路径，则称为强连通图。有向图中的极大连通子图称为其强连通分量。
• 网：边带权值的图称为网
• 图的存储：
  邻接矩阵：假设一个图中有n个节点，!则使用n阶矩阵来存储这个图中各节点的关系，规则是若节点到节点有连线，!则矩阵Ri,j=1，否则为0，示例如下图所示

• 邻接链表：用到了两个数据结构，先用维数组将图中所有顶点存储起来，而后，对此一维数组的每个顶点元素，使用链表挂上其出度到达的结点的编号和权值，示例如下图所示：

• 存储特点:图中的顶点数决定了邻接矩阵的阶和邻接表中的单链表数目，边数的多少决定了单链表中的结点数，用邻接矩阵存储。而不影响邻接矩阵的规模，因此采用何种存储方式与有向图、无向图没有区别，要看图的边数和顶点数，完全图适合采用邻接矩阵存储。
• 图的遍历是指从图的任意节点出发，沿着某条搜索路径对图中所有节点进行访问且只访问一次，分为以下两种方式：
  （1）深度优先遍历：从任一顶点出发，遍历到底，直至返回，再选取任一其他节点出发，重复这个过程直至遍历完整个图；
  （2）广度优先遍历: 先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。

• 图的最小生成树假设有n个节点，那么这个图的最小生成树有n-1条边 (不会形成环路，是树非图)，这n-1条边应该会将所有顶点都连接成一个树，并且这些边的权值之和最小，因此称为最小生成树。共有下列两种算法：
  （1）普里姆算法：从任意顶点出发，找出与其邻接的边权值最小的，此时此边的另外一个顶点自动加入树集合中，而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的，同样此边的另外一个顶点加入树集合中，依次递归，直至图中所有顶点都加入树集合中，此时此树就是该图的最小生成树。普里姆算法的时间复杂度为o(n^2)，与图中的边数无关，因此该算法适合于求边稠密的网的最小生成树。
  （2）克鲁斯卡尔算法：这个算法是从边出发的，因为本质是选取权值最(推荐)小的n-1条边，因此，就将边按权值大小排序，依次选取权值最小的边，直至囊括所有节点，要注意每次选边后要检查不能形成环路。克鲁斯卡尔算法的时间复杂度为o(eloge)，与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。

• 拓扑序列：若图中一个节点入度为0，则应该最先执行此活动，而后删除掉此节点和其关联的有向边，再去找图中其他没有入度的结点，执行活动，依次进行，示例如下(有点类似于进程的前趋图原理)
• 工具与技术：
  关键路径法关键路径：是项目的最短工期，但却是从开始到结束时间最长的路径。进度网络图中可能有多条关键路径，因为活动会变化，因此关键路径也在不断变化中关键活动：关键路径上的活动，最早开始时间=最晚开始时间。通常，每个节点的活动会有如下几个时间：
  （1）最早开始时间 (ES)某项活动能够开始的最早时间
  （2）某项活动能够完成的最早时间。EF=ES+工期最早结束时间(EF)
  （3）最迟结束时间(LF)。为了使项目按时完成，某项活动必须完成的最迟时间。
  （4）最迟开始时间(LS)。为了使项目按时完成，某项活动必须开始的最迟时间。LS=LF-工期
• 总浮动时间:在不延误项目完工时间且不违反进度制约因素的前提下，活动可以从最早开始时间推迟或拖延的时间量，就是该活动的进度灵活性。正常情况下，关键活动的总浮动时间为零。
• 总浮动时间=最迟开始LS-最早开始ES 或最迟完成LF-最早完成EF 或关键路径非关键路径时长。
• 自由浮动时间:是指在不延误任何紧后活动的最早开始时间且不违反进度制约因素的前提下，活动可以从最早开始时间推迟或拖延的时间量。
• 自由浮动时间=紧后活动最早开始时间的最小值-本活动的最早完成时间。

3.2 查找

3.2.1 顺序查找

• 顺序查找的思想：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败。
• 平均查找长度为
• 时间复杂度为O(n)。

3.2.2 折半查找

• 折半查找只适用于待查找序列中的元素是有序排列的情况。
• 设查找表的元素存储在一维数组r[1..n]中，在表中元素已经按照关键字递增或递减)方式排序的情况下，进行折半查找的方法是：
  1、首先将待查元素的关键字 (key) 值与表r中间位置上 (下标为mid) 记录的关键字进行比较，若相等，则查找成功；
  2、若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1..n]中，下一步应在后半个子表中查找；
  3、若key<r[mid].key，说明待查记录只可能在前半个子表rl1..mid-1]中，下一步应在r的前半个子表中查找；
  4、重复上述步骤，逐步缩小范围，直到查找成功或子表为空失败时为止。要注意两点:中间值位置求出若为小数，应该向下取整，即4.5=4，非四舍五入中间值已经比较过不相等，在划分下一次比较区间时，无需将中间值位置再纳入下一次比较区间。
• 折半查找的时间复杂度为

3.2.3 哈希表

• 哈希表通过一个以记录的关键字为自变量的函数 (称为哈希函数)得到该记录的存储地址，所以在哈希表中进行查找操作时，需要用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。

• 哈希函数产生了冲突的解决方法如下
  1.开放定址法： Hi=(H(key)+di) % m i=1,2,..., k(km - 1)其中，H(key)为哈希函数;m 为哈希表表长；di为增量序列常见的增量序列有以下3 种。
  (1) d =1,2,3,··,m-1，称为线性探测再散列；
  (2) 二次探测再散列；
  (3) d=伪随机数序列，称为随机探测再散列。
  2.链地址法。它在查找表的每一个记录中增加一个链域，链域中存放下一个具有相同哈希函数值的记录的存储地址。利用链域，就把若千个发生冲突的记录链接在一个链表内。当链域的值为NULL时，表示已没有后继记录了。因此，对于发生冲突时的查找和插入操作就跟线性表一样了
  3.再哈希法: 在同义词发生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生聚集现象，但增加了计算时间。
  4.建立一个公共溢出区。无论由哈希函数得到的哈希地址是什么，一旦发生冲突都填入到公共溢出区中

3.3 排序

3.3.1 直接插入排序

• 要注意的是，前提条件是前i-1个元素是有序的第i个元素依次从第i-1个元素而后插入，插入位置及其后往前比较，直到找到一个比第i个元素值小的元素的元素依次向后移动。
• 当给出一队无序的元素时，首先，应该将第1个元素看做是一个有序的队列，而后从第2个元素起，按插入排序规则，依次与前面的元素进行比较，直到找到一个小于他的值，才插入。示例如下图所示:下图中，59依次向前比较，先和68比较，再和57比较，发现57比他小，才插入：

3.3.2 希尔排序

• 希尔排序又称“缩小增量排序“是对直接插入排序方法的改进。
• 希尔排序的基本思想是：先将整个待排记录序列分割成若千子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入。
• 排序具体做法是：先取一个小于n 的整数d1作为第一个增量把文件的全部记录分成d1个组，将所有距离为d1 倍数的记录放在同一个组中，在各组内进行直接插入排序;然后取第二个增量d2(d2<d1)，重复上述分组和排序工作，依此类推，直至所取的增量di=1(di < di-1< ...< d2<d1)，即所有记录放在同一组进行直接插入排序为止。
• 按上述，希尔排序实际是为了解决大数据的排序问题当待排序的数据很多时，使用直接插入排序效率很低，因此，采取分组的方法，使问题细化，可以提高效率，适用于多数据。

3.3.3 简单选择排序

• n个记录进行简单选择排序的基本方法是: 通过n - i(1<=i<=n)次关键字之间的比较，从n - i +1个记录中选出关键字最小的记录，并和第i 个记录进行交换，当i等于n时所有记录有序排列。按上述，本质就是每次选择出最小的元素进行交换主要是选择比较过程交换过程只有一次。示例如下：

3.3.4 堆排序

• 堆排序的基本思想是:对一组待排序记录的关键字，首先按堆的定义排成一个序列(即建立初始堆)，从而可以输出堆顶的最大关键字(对于大根堆而言)，然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止。
• 为序列(55,60,40,10,80,65,15,5,75) 建立初始大根堆的过程如图所示

• 由上图可知，首先将给出的数组按完全二叉树规则建立，而后，找到此完全又树的最后一个非叶子节点 (也即最后一颗子树)，比较此非叶子节点和其两个孩子结点的大小，若小，则与其孩子结点中最大的结点进行交换;依据此规则再去找倒数第二个非叶子节点;这是只有一层的情况，当涉及到多层次时又打破了之前的堆，因此，又要进行变换。
• 建立初始堆后，开始排序，每次取走堆顶元素 (必然是最大的)而后将堆中最后一个元素移入堆顶，而后按照初始建堆中的方法与其孩子结点比较大小依次向下判断交换成为一个新的堆，再取走堆顶元素，重复此过程。堆排序适用于在多个元素中找出前几名的方案设计，因为堆排序是选择排序而且选择出前几名的效率很高。

3.3.5 冒泡排序

• n个记录进行冒泡排序的方法是:首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字依此类推，直至第n- 1个记录和第n 个记录的关键字比较过为止。上述过程称为一趟冒泡排序，其结果是关键字最大的记录被交换到第n 个记录的位置上。然后进行第二趟冒泡排序，对前n - 1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n - 1个记录的位置上。最多进行n - 1 趟所有记录有序排列。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。
• 示例给的是从后往前排序，也是可以的，需要从最后两个元素开始进行比较，将较小的元素交换到前面去，依次进行比较交换。比较是为了交换，交换次数很多。区分冒泡排序和简单选择排序。

3.3.6 快速排序

• 快速排序是将n个记录分成两块，再递归，实际分成两块的方法如图所示:设定一个基准为57，设定两个指针high=1，low=n，从low指向的第n个元素开始，与基准值进行比较，若小于基准值，则与基准进行交换low--，此时，转而从high指向的第1个元素开始和基准值进行比较，若大于基准值，则和基准值进行交换此时，又转而从low一指向的值和基准进行比较，重复上述过程。
• 要注意的是:每次都是和基准值进行比较，因此最终是以基准值为中间，将队列分成两块。只有当和基准值发生了交换，才变换high和low指针的计数，否则会一直low-下去
• 上图中，最终以57为界，左边都是小于57的元素右边都是大于57的元素，完成一次快速排序，接着对两块再分别进行递归即可

3.3.7 归并排序

• 所谓“归并”是将两个或两个以上的有序文件合并成为一个新的有序文件归并排序的一种实现方法是把一个有n 个记录的无序文件看成是由n 个长度为1的有序子文件组成的文件，然后进行两两归并，得到[n/21个长度为2或1的有序文件，再两两归并，如此重复，直至最后形成包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。要仔细理解上述过程，一般归并排序都是用来合并多个线性表的，对单列数据，二路归并排序可以对元素进行两两合并，示例如下!对第三次归并，将52与28比较，28小，放入新表头，52再与33比较，33放入新表，52再与72比较，52放入新表，57再与72比较，57放入新表.....

3.3.8 基数排序

• 基数排序是基于多个关键字来进行多轮排序的，本质也是将问题细分，如图例子，分别按个位、十位、百位的大小作为关键字进行了三轮排序，最终得出结果。
• 基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位来分解。

3.3.9 内部排序算法总结

1. 若待排序的记录数目n 较小，可采用直接插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因此当记录本身信息量较大时，用简单选择排序方法较好。
2. 若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序
3. 当n 很大且关键字的位数较少时，采用链式基数排序较好。
4. 若n 较大，则应采用时间复杂度为o(nlogn)的排序方法，例如快速排序、堆排序或归并排序。

3.3.10 算法特性

• 算法 (Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性:
  (1)有穷性一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束且每一步都可在有穷时间内完成确定性。算法中的每一条指令必须有确切的含义，理解时不会产生二义性.
  (2)并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
  (3)可行性。一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  (4)输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合.
  (5)输出。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

【软考数据库】第一章 计算机系统基础知识 

【软考数据库】第二章 程序语言基础知识