数据结构

数据结构绪论知识梳理，包括数据结构的基本术语、数据结构三要素、算法三部分内容，需要的可以看下。

绪论

• 基本术语
  • 数据
    • 信息的载体，计算机中所存储信息的集合
  • 数据元素
    • 数据的基本单位
    • 由数据项组成，数据项是其最小的不可分割是最小单元
  • 数据对象
    • 具有相同性质的数据元素的集合，数据的一个子集
  • 数据类型
    • 一个值的集合和定义在此集合上的一组操作的总称
    • 原子类型：其值不可再分
    • 结构类型：可以再分解成若干成分的数据类型
    • 抽象数据类型：抽象数据组织及与之相关的操作
  • 数据结构
    • 相互之间存在着一种或多种特定关系的数据元素的集合
    • 三种类型
      • 逻辑结构
      • 存储结构
      • 数据的运算
• 数据结构三要素
  • 逻辑结构
  • 存储结构
    • 顺序存储
      • 逻辑物理都相邻
      • 优点：实现随机存取
      • 缺点：只能使用相邻的一整块存储单元
    • 链式存储
      • 逻辑相邻，物理不一定相邻，使用指针表示逻辑关系
      • 优点：不会产生碎片，充分利用存储单元
      • 缺点：存储指针会占用额外的存储空间，只能顺序存取
    • 索引存储
      • 存储元素信息和附加的索引表。
      • 优点：检索速度快
      • 缺点：附加的索引表额外占用存储空间，插入删除元素是也要修改索引表花费时间较多
    • 散列存储
      • 根据元素的关键字直接计算出该元素的存储地址，又称哈希存储
      • 优点：数据检索、增加和删除速度较快
      • 缺点：可能出现元素存储单元的冲突，增加时间和空间开销。
  • 数据运算
    • 施加在数据上的运算包括运算的实现和定义
    • 定义针对逻辑结构，运算功能
    • 实现针对存储结构，运算具体操作步骤
• 算法
  • 对特定问题求解步骤的一种描述，指令的有限序列，每条指令表示一个或多个操作
  • 特性
    • 有穷性
    • 确定性
    • 可行性
    • 输入
    • 输出
  • 达到目标
    • 正确性
    • 可读性
    • 健壮性
    • 效率与低存储量需求
  • 效率
    • 时间复杂度
      • 语句被重复执行的次数
    • 空间复杂度
      • 算法耗费的存储空间

线性表

• 基本定义
  • 具有相同数据类型的n个数据元素组成的有限序列
  • 基本特性
    • 除第一个元素外每个元素有且仅有一个直接前驱
    • 除最后一个元素外每个元素有且仅有一个直接后继
  • 线性表是一个逻辑结构
• 顺序存储
  • 又被称为顺序表，是一种存储结构，数据逻辑物理都相邻
  • 定义结构
    • 静态结构
    • 动态结构
  • 插入操作
    • 元素移动情况
      • 最好：O(1)
      • 最坏：O(n)
      • 平均移动节点次数：n/2
      • 插入时间复杂度为O(n)
  • 删除操作
    • 元素移动情况
      • 最好：O(1)
      • 最坏：O(n)
      • 平均移动节点次数：(n-1)/2
      • 删除时间复杂度为O(n)
  • 按值查找
    • 元素移动情况
      • 最好：O(1)
      • 最坏：O(n)
      • 平均移动节点次数：(n+1)/2
      • 按值查找时间复杂度为O(n)
• 链式存储
  • 通过指针将数据串连在一起，不能进行顺序存取，在进行插入删除时修改指针即可。又称之为链表是一种存储结构
  • 单链表
    • 通过一组任意的存储单元来存储线性表中的数据元素。每个链表结点，还需存放指向后一结点的指针。
    • 优点：解决了数据连续存储带来的碎片问题
    • 缺点：存储指针域存在浪费空间的问题，数据离散存储，是一种非随机存取的存储结构，找到特定的结点需从表头开始。
    • 头结点：第一个结点之前附加的结点，数据域不存储信息。（1）对第一个结点的操作以其他结点一致。 （2）对空表和非空表的操作得到了统一
    • 头指针：指向第一个结点的指针，为NULL时，线性表是一个空表。不管是否有头结点，头指针都指向链表的第一个结点。
    • 操作实现
      • 头插法建立单链表
        • 将新结点插入链表表头
        • 时间复杂度O(n)
      • 尾插法建立单链表
        • 新结点插入链表表尾，需新增一个尾指针始终指向尾结点
        • 时间复杂度O(n)
      • 按序号查找结点值
        • 从第一个结点出发，顺next域进行搜索，直到找到第i个结点
        • 时间复杂度O(n)
      • 按值查找表结点
        • 从第一个结点出发，顺data域进行搜索，直到所需值
        • 时间复杂度O(n)
      • 插入结点
        • 将对应数据的值插入到相应的第i个结点的位置。
        • 时间复杂度O(n)
      • 删除结点
        • 将对应位置的第i个结点删除
        • 时间复杂度O(n)
      • 求表长
        • 计算单链表中数据结点的个数。
        • 时间复杂度O(n)
  • 双链表
    • 含有两个指针域的链表，prior执行前驱结点，next指向后继结点
    • 操作实现
      • 除插入和删除外其余操作类似
      • 插入
        • 时间复杂度0(1)
      • 删除
        • 时间复杂度0(1)
  • 循环链表
    • 循环单链表
      • 表中最后一个结点的指针执行有节点的数据域
      • 插入、删除与单链表相似，但不用判断是否为表尾
      • 设置尾指针使得对表头和表尾的操作时间复杂度为O(1)
    • 循环双链表
      • 头结点的prior指针需指向表尾结点，为空表时头结点的prior和next都等于L
  • 静态链表
    • 采用数组描述线性表的链式存储结构，但结点的指针域是指数组的下标。
    • 使用需预先分配一个连续的存储空间
    • 结束标志是next==1
• 顺序表和链表比较
  • 读写方式
    • 顺序表
      • 顺序存取、随机存取
    • 链表
      • 只能在表头顺序存取元素
  • 逻辑结构和物理结构
    • 顺序表
      • 逻辑相邻，物理一定相邻
    • 链表
      • 逻辑相邻，物理不一定相邻
  • 查找、插入和删除
    • 顺序表
      • 按值查找
        • 无序O(n)
        • 有序O(log2n)
      • 按序号查找
        • O(1)
      • 插入删除
        • 平均移动半个表长元素
    • 链表
      • 按序号查找
        • O(n)
      • 插入删除
        • 修改对应结点指针域
  • 空间分配
    • 顺序表
      • 静态
        • 装满不能扩容，需预分配较大空间。过大浪费空间；过下造成溢出
      • 动态
        • 可以扩容，但操作效率低，若没有更大块的连续存储空间，就分配失败
    • 链表
      • 存储空间分配方便，操作灵活、高效

栈，队列

• 栈
  • 定义
    • 只允许在一段进行插入或删除的线性表，先进后出
    • 栈顶：进行插入删除的一段
    • 栈底：固定的不允许进行插入和删除的另一端
    • n个不同的元素进栈，出战元素的不同排列个数为
  • 顺序存储
    • 顺序存储的栈，利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时设置一个指针指示当前栈顶元素位置
    • 栈顶指针S.top，初始时设置为S.top=-1
    • 栈顶元素：S.data[S.top]
    • 进栈：不满时，栈顶指针+1，再将值送到栈顶指针。
    • 出站：不空时，先取栈顶元素值，再将栈顶指针-1
    • 栈空判断条件：S.top==-1
    • 栈满条件：S.top==MaxSize-1
    • 栈长：S.top+1
    • 共享栈
      • 两个顺序栈共享一个一维数组空间，栈底分别设置在共享空间的两端，向中间延伸
      • 可以更加有效的利用存储空间，存取数据的时间复杂度均为O(1)
  • 链式存储
    • 采用链式存储的栈称为链栈。
    • 优点：便于多个栈共享存储空间提高效率，不存在栈满上溢的情况
    • 链栈没有头结点，Lhead指向栈顶元素。
    • 便于结点的插入和删除，操作与链表类似，入栈与出站都在表头进行
• 队列
  • 也是一种操作受限的线性表，只允许在一段进行插入，另一端进行删除。
  • 操作特点：先进先出
  • 基本信息
    • 队头：允许进行删除的一段
    • 队尾：允许进行插入的一段
    • 空队列：不含任何元素的空表
  • 顺序存储
    • 分配一块连续的地址单元存放队列中的数据，附设队头指针front，队尾指针rear
    • 队空（初始状态）：Q.front==Q.rear==0
    • 进队：不满时，送值到队尾，队尾指针+1
    • 出队：不空时，取队头元素，队头指针+1
    • 会有假溢出的情况出现
  • 循环队列
    • 将队列视为一个环。
    • 初始：Q.front=Q.rear=0
    • 队首指针进1：Q.front=(Q.front+1)%MaxSize
    • 队尾指针进1：Q.rear=(Q.rear+1)%MaxSize
    • 队列长度：（Q.rear+MaxSize-Q.front)%MaxSize
    • 出队入队时指针都按顺时针方向进1
    • 判断队满队空
      • 牺牲一个存储单元
        • 当队头指针在队尾指针的下一位置时，作为队满的标志
        • 队满：（Q.rear+1)%MaxSize==Q.front
        • 队空：Q.front==Q.rear
        • 元素个数：（Q.rear-Q.front+MaxSize)%MaxSize
      • 增设元素个数数据成员
        • 队空：Q.size==0
        • 队满：Q.size==MaxSize
      • 增设tag数据元素
        • tag=0，删除导致Q.front==Q.rear，队列为空
        • tag=1，插入导致Q.front==Q.rear，队列为满
  • 链式存储
    • 队列的链式表示为链队列，同时带有队头指针和队尾指针的单链表
    • Q.front==Q.rear==NULL，队列为空
    • 常设置为带头结点的单链表，可以简化对队列的插入和删除操作
    • 使用链式结构存储队列，避免了存储分配不合理和“溢出”的问题
  • 双端队列
    • 队列两端都可以进行入队和出队操作的队列。
    • 进队操作：前端进队的元素排列在后端进队元素的前面
    • 输出受限双端队列：一端允许插入和删除，另一端仅允许插入
    • 输入受限双端队列：一端允许插入和删除，另一端仅允许删除
• 应用
  • 栈应用
    • 括号匹配
      • （1）设置空栈，顺序读入括号
      • （2）左括号：作为新的更急切的期待压入栈中
      • （3）右括号：消除最急切的期待，或不合法
    • 表达式求值
      • 扫描表达式，操作数进栈，扫描到操作符op，从栈中退出两个操作数Y和X，计算X opY，将计算结果压入栈中，继续扫描至扫描完成
    • 斐波那契数列
  • 队列应用
    • 层次遍历
      • （1）根节点入队
      • （2）队为空，结束遍历，否则重复（3）
      • （3）第一个结点入队，访问之。有左孩子，左孩子入队；有右孩子，右孩子入队。返回（2）
    • 计算机系统
      • 以队列作为数据缓冲区，解决主机与外部设备之间数据不匹配的问题
      • 以队列存储各种请求信息，解决有多用户引起的资源竞争问题
• 数组
  • 定义
    • 数组是由n个相同数据类型构成的有限序列。
    • 数组是线性表的推广，数组一旦被定义，其维数和维界就不再改变
  • 存储结构
    • 行优先存储
    • 列优先存储
• 特殊矩阵
  • 对称矩阵
  • 三角矩阵
    • 下三角数据存储
    • 上三角数据存储
  • 三对角矩阵
  • 稀疏矩阵
    • 将矩阵中的非零元素按照其行列以及对应值的顺序进行存储，三元组

串

• 基本概念
  • 串：由零个或多个字符组成的有限序列。序列中的内容可以是数、字母等其他字符。
  • 串的长度n，n=0时为空串
  • 字串：串中任意多个连续的字符组成的子序列
  • 主串：包含字串的串
  • 位置
    • 某个字符在串中的序号
    • 字串在主串中的位置用字串的第一个字符在主串中的位置表示
  • 空格串：由一个或多个空格组成的串
• 存储
  • 定长顺序存储
    • 为每一个串变量分配一个固定长度的存储区，即定长数组
    • 串长表示
      • 设置一个额外的变量存放串的长度
      • 在串后增加一个不计入串长度的结束标记字符"\0"
  • 堆分配存储
    • 是一组地址连续的存储单元，但是他们的存储空间是在程序执行过程中动态分配得到的
    • 在使用中通常使用malloc()和free()函数实现动态管理
  • 块链存储
    • 使用链表存储串值
    • 可以使用一个结点存放一个字符，也可以一个结点存放多个字符。
    • 每个结点称为块，整个链表称为块链结构。
• 模式匹配算法
  • 简单模式匹配算法
    • 在匹配不成功时，主串的指针返回到第二个字符。字串的指针回到第一个字符
    • 时间复杂度O(mn)
  • KMP算法
    • 计算字串的对应next数组的值
    • 根据next数组的值确定在匹配出错时，字串的移动情况。

树与二叉树

• 树
  • 定义
    • n个结点的有限集，n=0时为空树
    • 有且仅有一个特定的根节点
    • 当n>1是，剩余结点可分为m个互不相交的有限集，每个集合本身是一棵树，也是根的子树
  • 特点
    • 根节点没有前驱，除根节点外的所有节点有且仅有一个前驱
    • 所有节点可以有零个或多个后继
  • 术语
    • 祖先、子孙、双亲、孩子、兄弟
    • 度
      • 结点孩子的个数
      • 结点的最大度数是树的度
    • 分支结点：度>0的结点
    • 叶子结点：度=0的结点
    • 结点深度：从根节点开始自顶向上逐层累加
    • 结点高度：从叶节点开始自底向上逐层累加
    • 有序树：结点的左右顺序不能互换
    • 无序树：结点的左右顺序可以互换
    • 路径：两结点之间经过的结点序列构成，结点数是路径的长度
  • 性质
    • 结点数=度数和+1
  • 存储结构
    • 双亲表示
      • 采用一组连续的空间来存储每个结点，同时在每个结点中增加一个伪指针，表示结点双亲在数组中的位置。
      • 可以较快的找到每个结点的双亲结点，但是寻找结点的孩子时需要遍历整个结构
    • 孩子表示
      • 每个结点的孩子都用单链表连接成一个线性结构
      • 寻找子女非常简单，而寻找双亲的操作需要遍历n个链表中孩子结点指针域所指向的n个孩子链表
    • 兄弟孩子表示
      • 又称为二叉树表示法。每个结点包括三个部分：结点值，结点指向第一个孩子节点的指针，指向下一个兄弟结点的指针。
      • 这种结构查找双亲结点较为复杂，可以通过增设一个parent域执行其父结点。
  • 遍历
    • 树
      • 先根
        • 根节点访问，遍历子树也按照先根后结点的顺序
      • 后根
        • 先遍历子树再遍历根，更小一级的子树也是按照这种方式进行
    • 森林
      • 先序
        • 第一棵树的根节点
        • 先序遍历第一棵树根节点子树
        • 先序遍历除第一棵子树外的其他子树构成的森林
      • 中序
        • 中序遍历第一棵子树的根节点子树森林
        • 第一棵树根节点
        • 中序遍历除第一棵子树外的剩余子树构成的森林
    • 树、森林和二叉树遍历对应
• 二叉树
  • 定义
    • 每个结点至多有两棵子树，子树有左右之分，其次序不能颠倒。与度为2的树不同
  • 特殊二叉树
    • 满二叉树
    • 完全二叉树
      • 最后一层不满的二叉树，度为1结点只可能有一个且仅有左孩子没有右孩子
    • 二叉排序树
      • 左子树上所有节点的关键字均小于根节点的关键字，右子树都大于
    • 平衡二叉树
      • 树上任意结点的左子树和右子树的深度之差不超过1
  • 性质
    • 完全二叉树
  • 存储结构
    • 顺序
      • 用一组连续的存储单元一次自上而下，自左至右的存储二叉树上的结点，用0表示不存在的空结点
    • 链式
      • 二叉链表包含三个域：数据域data、左指针域lchild、右指针域rchild
      • 在n个结点的二叉链表中，含有n+1个空链域
  • 遍历
    • 先序
      • 根、左子树、右子树
    • 中序
      • 左子树、根、右子树
    • 后序
      • 左子树、右子树、根
    • 层次
      • 按照从上到下，从左到右的顺序访问每个结点
• 线索二叉树
  • 概念
    • 是以一定的规则将二叉树中的结点排列成一个线性序列
    • 采用链表的方式，其标志域为0时指示左孩子，标志域为1时指示右孩子
  • 线索二叉树构造
    • 线索化是将链表中的空指针改为执行前驱或后继的线索，实质是遍历一次二叉树
    • 中序
    • 先序，后序
• 树森林二叉树
  • 树转换为二叉树
    • 规则：左孩子右兄弟
    • 画法
      • 兄弟结点之间加一条线
      • 每个结点只保留与第一个孩子的连线
      • 以树根为轴心，顺时针旋转45度
  • 森林转换成二叉树
    • 每个数转换成相应的二叉树
    • 每棵树的根视为兄弟管理，树根之间加一根连线
    • 以第一棵树根为轴心顺时针旋转45度
• 哈夫曼树
  • 树的结点被赋予表示某种意义的数值，称为结点的权
  • 带权路径长度：从树的根到任意结点的路径长度与该节点上权值的乘积
  • 含有n个带权叶节点的二叉树中，带权路径长度最小的称为哈夫曼树
  • 构造方法
    • 在结点值中，选择两个最小值作为新结点的左右子树，其权值之和作为根节点的值
    • 在新的权值中选择两个最小的作为下一个左右孩子。
  • 特点
    • 每个初始结点最终都成为叶节点，权值越小的结点到根节点的路径长度越大
    • 共新建了n-1个结点，结点总数为2n-1
    • 每次构造都选择2棵树作为新结点的孩子，不存在度为1的结点
  • 编码
    • 每一条边都按照左1右0，或右1左0的方式进行编码
    • 为前缀编码：没有一个编码数另一编码的前缀

图

• 定义
  • 由顶点集V和边集E组成
  • 不可以是空图，图中不能没有一个顶点，但是可以没有边
  • 基本概念
    • 有向图
      • 边是顶点的有序对，用<v,w>
      • 强连通：在两个顶点之间存在相反的连通路径
      • 强连通图：每一对顶点都是强连通
      • 强连通分量：有向图中的极大强连通子图
    • 无向图
      • 边是顶点的无序对，用(v,w)
      • 连通：两顶点之间存在路径
      • 连通图：任意两定点是连通的，否则是非连通图
      • 连通分量：无向图中的极大连通子图
    • 简单图：不存在重复边，不存在顶点到自身的边
    • 多重图：图中某两个顶点之间的边数大于1，又允许顶点通过一条边和自身相关联
    • 完全图
      • 对无向图，任意两个顶点之间都存在边
      • 对有向图，任意两个顶点之间都存在方向相反的两条弧
    • 子图：
    • 生成树：是包含图中全部顶点的一个极小连通子图
    • 生成森林：非连通图中，连通分量的生成树所构成
    • 度
      • 无向图中顶点的度与其边的条数有关，
      • 有向图
        • 入度：以顶点为终点
        • 出度：以顶点为起点
        • 度=入度+出度，
    • 边的权和网：每条边都可以标上具有某种含义的数值，称为权值，这种边上带有权值的图称为带权图，也称为网
    • 边数少的图称为稀疏图，反之则为稠密图。两者之间的分别是模糊的，是相对而言的
    • 路径：连接两顶点之间的顶点序列
    • 路径长度：顶点序列中顶点的数量
    • 回路：第一个顶点和最后一个顶点相同的路径
    • 简单回路：路径序列中没有重复的顶点，除最后一个顶点和第一个顶点之外其他的顶点都不相同的回路是简单回路
    • 距离：从顶点1到顶点2的最短路径，若不存在最短路径则记该距离为无穷
    • 有向树：一个顶点的入度为零，其余顶点入度均为1的有向图
• 存储
  • 邻接矩阵
    • 用一个一维数组存储图中顶点的信息，用二维数组存储图中边的信息
    • 不带权图
    • 带权图
    • 特点
      • 无向图的邻接矩阵是对称的，规模较大的可以使用压缩存储
      • 空间复杂度O(n)
      • 有向图
        • 出度第i行非零元素的个数
        • 入度第i列非零元素的个数
      • 适合表示稠密图
  • 邻接表
    • 对图中的每一个顶点建立一个单链表，单链表中的结点表示依附于顶点的边，这个单链表称为顶点的边表。边表的头指针和顶点的数据信息是按照顺序存储
    • 特点
      • 存储空间
        • 无向图：
        • 有向图：
      • 适合表示稀疏图
      • 有向图
        • 出度：单链表中元素的数据个数
        • 入度：遍历整个邻接表
      • 表示不唯一，在结点对应的单链表中连接次序可以互换
  • 十字链表
    • 有向图的一种链式存储结构
    • 弧结点
      • tailvex：弧尾在图中位置
      • headvex：弧头在图中位置
      • hlink：指向弧头相同的下一条弧
      • tlink：指向弧尾相同的下一条弧
    • 顶点结点
      • data：顶点相关的数据信息
      • firstin：顶点为弧头的第一个弧结点
      • firstout：顶点为弧尾的第一个弧结点
    • 顶点结点之间是顺序存储的
  • 邻接多重表
    • 无向图的链式存储结构
    • 边结点
      • mark：标记该条边是否被搜索过
      • ivex jvex：该边依附的两个顶点在图中的位置
      • ilink：下一条依附于顶点ivex的边
      • jlink：下一条依附于顶点jvex的边
    • 同一条边，只用一个结点表示，在邻接表中用两个顶点表示
• 遍历
  • 广度优先搜索（BFS）
    • 从某一顶点开始，由近及远的访问和该顶点有路径相连通且路径长度为1,2，...n
    • 是一种分层查找的过程，借助一个辅助队列，存储正在访问顶点的下一层顶点
    • 性能分析
      • 空间复杂度
      • 时间复杂度
        • 邻接表
        • 邻接矩阵
    • 求解最短路径
      • 求非带权图两顶点的最短路径，
    • 广度优先生成树
      • 邻接矩阵的广度优先生成树是唯一的
      • 邻接表的广度优先生成树是不唯一的
  • 深度优先搜索（DFS）
    • 访问图某一起始顶点v，然后由v出发，访问与v邻接且未被访问过的任一顶点w，再访问与w邻接且未被访问的任一顶点q，重复改过程。
    • 性能分析
      • 空间复杂度：
      • 时间复杂度
        • 邻接矩阵：
        • 邻接表：
    • 深度优先生成树
      • 邻接表存储的是不唯一的
  • 遍历与连通性
    • 无向图
      • 连通的，从任意结点出发仅需一次就能访问所有顶点
      • 非连通的，一次遍历只能访问到该顶点所在的连通分量的所有顶点
    • 有向图：若从初始点到图中的每个顶点都有路径，才能够访问到图中的所有顶点，否则不能访问到所有顶点。
• 相关应用
  • 最小生成树
    • 对于带权连通无向图，生成树不同，每棵树的权也可能不同，设W为图所有生成树的集合，则再集合当中，权值和最小的树称为图的最小生成树
    • 性质
      • 不是惟一的，对于无向连通图 边+1=顶点，最小生成树是他本身
      • 权值之和是唯一的
      • 边+1=顶点
    • Prim算法
      • 初始时，任取一顶点加入树中，选择与他距离最近的一个顶点加入集合中，依此重复
      • 时间复杂度：
      • 适合求边稠密的图
    • Kruskal算法
      • 按照权值递增顺序选择合适的边构造最小树的方法
      • 时间复杂度：
      • 边稀疏顶点较多的图
  • 最短路径
    • 带权图时，从一顶点到另一顶点的路径之和，定义为改路径的带权路径长度
    • 求解依赖于：两点之间的最短路径包含了路径上其他顶点间的最短路径
    • Dijkstra算法
      • 求解单源最短路径，即某一顶点到其他各顶点的最短路径
      • 设置集合S，记录已求得的最短路径的顶点，把源点v0放在集合S中，集合中每并入Vi，都要修改源点到集合当中
      • 辅助数组
        • dist[]：记录源点v0到其他各点的最短路径长度
        • path[]：从源点到顶点i之间的最短路径的前驱结点
      • 时间复杂度
        • 邻接矩阵和带权邻接表：
      • 不适用于边上带负值的图
    • Floyd算法
      • 求每对顶点间的最短路径
      • 实现：实际是一个迭代的过程，通过递推的方式产生n阶方阵序列，每一次在 i 和 j 两个顶点之间的最短路径上考虑多一个顶点，经过n次迭代之后，就可以得到 i 和 j 之间最短路径
      • 时间复杂度
      • 允许带负权值的边，但是不允许有包含负权值的边组成的回路
  • 有向无环图描述表达式
    • 有向无环图：一个有向图中不存在环
    • 将表达式中相同的子式进行共享，节省存储空间
  • 拓扑排序
    • AOV网：用DAG图表示一个工程，其顶点表示活动，两顶点之间的有向边必须头先于尾活动的一种关系，称这种有向图为顶点表示活动的网络。
    • 定义
      • 有向无环图的顶点组成的序列
      • 使得若存在一条从顶点B到顶点A的路径，则再排序中顶点A出现在顶点B的后面
    • 满足要求
      • 每个顶点只出现一次
      • A在拓扑序列中在B的前面，则在图中不存在从B到A的边
    • 排序方式
      • 选择一个没有前驱的顶点并输出
      • 从网中删除该顶点和所有以他为起点的有向边
      • 重复前两个步骤，直到网中没有顶点，若始终有点存在，说明图中存在环
    • 时间复杂度
      • 邻接表：
      • 邻接矩阵：
    • 逆拓扑排序
      • 选择没有后继（出度为0）的顶点并输出
      • 删除改顶点和所有以他为终点的有向边
  • 关键路径
    • AOE网
      • 带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成改活动的开销（完成活动所需时间），称之为用边表示活动的网络
      • 性质
        • 只有在某顶点所代表是时间发生后，从该顶点出发的有向边所代表的活动才能开始
        • 只有在进入某顶点的个有向边所代表的活动都已经结束，该顶点所代表的事件才能发生
      • 在该图当中仅有一个入度为0的顶点，称为开始顶点（源点）代表整个工程的开始。仅存在一个出度为0的顶点，称为结束顶点（汇点）代表整个工程的结束
    • 关键活动
      • 从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
      • 完成整个工程的最短时间就是关键路径的长度，关键路径上关键活动所花费的时间。
      • 关键活动影响整个工程的时间，若关键活动不能按时完成，则整个工程的完成时间就会延长，只要找到关键活动，就找到关键路径，也就可以得出最短完成时间
      • 参量定义
        • 事件Vk的最早发生时间ve(k)
          • 从源点到顶点Vk的最长路径长度，Vk的最早发生时间决定了所有从Vk开始的活动能够开工的最早时间
          • ve()的计算是按照从前往后的顺序进行的，可以在拓扑结构的顺序上进行
        • 事件Vk的最迟发生时间vl(k)
          • 在不推迟整个工程完成的前提下，保证它的后继事件Vj在其最迟发生时间vl(j)能够发生时，该事件最迟必须发生的时间
          • vl(汇点)=ve(汇点)
          • 在计算该值时，需要增设一个栈记录拓扑序列
        • 活动ai的最早开始时间e(i)
          • 该活动弧的起点所表示时间的最早发生时间
        • 活动ai的最迟开始时间l(i)
          • 该活动弧的终点所表示事件的最迟发生时间与该活动所需时间的差
        • 活动最迟开始时间和最早开始时间的差额
          • 活动完成时间的余量，即工程总体完成时间不变，活动可以拖延是时间
          • 若活动的时间余量为零，说明活动必须如期完成，则该活动为关键活动
      • 求解步骤
        • 从源点出发，令ve(源点)=0，按拓扑有序求其余顶点的最早发生时间ve()
        • 从汇点出发，令vl(汇点)=ve(汇点)，按你拓扑有序求其余顶点的最迟发生时间vl()
        • 根据各顶点的ve()求所有弧的最早开始时间 e()
        • 根据各顶点的vl()求所有弧的最迟开始时间 l()
        • 求AOE网中所有活动的差额，找出所有d()=0的活动构成关键路径
      • 注意
        • 关键路径上的所有活动都是关键的，是决定整个工程的关键因素，可以通过加快关键活动来缩短整个工程的工期，但不能任意缩短，缩短过小会使关键搞活动变成非关键活动
        • 关键路径并不唯一，只提高一条关键路径上的关键活动速度不能缩短整个活动的工期，要加快包括在所有关键路径上的关键活动

查找

• 基本概念
  • 查找：在数据集合中寻找满足某种条件的数据元素的过程，有查找成功和失败两种情况
  • 查找表：用于查找的数据集合，由同一类型的数据元素组成，可以是数组或链表等数据类型
  • 静态查找表：不用动态的修改查找表
  • 动态查找表：需要动态的进行插入或删除的查找表
  • 关键字：数据元素中唯一标识该数据元素的某个数据项的值，基于关键字的查找，查找结果是唯一的
  • 平均查找长度：所有查找过程中进行关键字的比较次数的平均值（是衡量查找算法效率的重要指标）
• 静态查找
  • 顺序查找
    • 又称为线性查找，适用于线性表和链表
    • 一般线性表
      • 基本思想：从线性表的一端开始，逐个检查关键字是否满足给定条件。
      • 可以在算法中引入"哨兵"，来避免不必要的判断语句
      • 对于有n个元素的表，对于给定值key与第i个元素相等，则进行n-i+1次关键字比较
      • 查找平均长度
        • 成功
          • 概率不相等：
          • 概率相等：
        • 失败
      • 通常情况下，查找概率不相等，如果可以预先得知每个记录的查找概率，可以按照查找概率重新进行排序
      • 优缺点
        • 优点：对数据元素的存储没有要求，顺序链式均可以
        • 缺点：当n较大时，平均查找长度较大
        • 对于表中记录的有序性没有要求，线性的链表只能进行顺序查找
    • 有序线性表
      • 查找前已知表时关键字有序的，查找失败时可以不用再比较到表的另一端就能够饭后查找失败的信息，可以降低平均查找长度
      • 基本思想：当关键字key<第i个关键字，>第i+1个关键字，那么就可以返回查找失败
      • 查找平均长度
        • 成功
          • 概率不相等：
          • 概率相等：
        • 失败
  • 折半查找
    • 仅适用于有序的顺序表
    • 基本思想：将给定值key与表中间位置的元素比较，若相等，查找成功；不成功，查找元素只能在中间元素以外的前半部分或后半部分的中间位置进行查找。
    • 判定树
      • 折半查找的过程可以用二叉树来描述
      • 树中的每一个圆形结点表示一个记录，结点中的值为该记录的关键字值，树最下面的结点是方形的代表查找不成功的情况。
    • 查找平均长度
      • 成功
      • 失败
        • 将成功的1/n，该为方形结点（不成功）情况1/n+1
    • 时间复杂度
      • 平均情况下不顺序查找的效率高
    • 该方法需要方便的定位查找区域，要求线性表必须可以随机存取，仅适用于有序的顺序表
  • 分块查找
    • 又称为索引顺序查找，吸取了顺序查找和折半查找的优点，既有动态结构，又适用于快速查找
    • 基本思想：将查找表分为若干块，块内的元素可以无序，但是块间是有序的，前一个块的最大关键字<下一个块的最下关键字。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素地址，按照关键字有序排列
    • 步骤
      • 在索引表中确定待查记录所在的块，可以顺序查找或折半查找
      • 在块内顺序查找
    • 查找平均长度
      • 成功
        • 索引表采用顺序查找：
        • 索引表采用折半查找：
• 动态查找
  • 二叉排序树
    • 定义
      • 若左子树非空，左子树所有节点值均小于根节点的值
      • 若右子树非空，右子树所有节点值均大于根节点的值
      • 左右子树也分别是一棵二叉排序树
    • 查找
      • 从根节点开始，沿着某个分支逐层向下比较的过程
      • 若树非空，先与根节点比较，相等查找成功；不等，小于与左子树比较，大于与右子树比较
    • 插入
      • 原二叉树为空，直接插入结点，小于根节点插入左子树，大于根节点插入右子树，新插入的是叶节点，是查找失败时查找路径上访问的最后一个结点的右孩子或左孩子
    • 构造：从一颗空树出发，一次输入元素，将他们插入二叉排序树中的合适位置。
    • 删除
      • 删除时，不能把该节点为根的子树上的结点都删除，必须先把删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表连接起来，确保二叉排序树的性质不会丢失
      • 情况
        • 叶节点，直接删除
        • z结点只有一颗左子树或右子树，z的子树称为z父结点的子树
        • z有左右两棵子树，令z的直接后继代替z，然后从二叉排序树中删除直接后继，转换为前两种情况
    • 效率分析
      • 主要取决于树的高度
        • 左右子树高度差绝对值不超过1，平均查找长度为
        • 只有左或右子树，平均查找长度
        • 最坏的情况，二叉排序树的输入序列是有序的，会形成单只树，性能会显著变坏
      • 不需移动结点，就可以修改指针就可以完成插入和删除操作，平均执行时间
      • 二分查找对象是有序顺序表，删除和插入结点，代价
      • 有序表是静态表，采用顺序表，查找使用二分查找有序表是动态表，采用二叉排序树
  • 二叉平衡树
    • 定义
      • 任意结点的左右子树高度差绝对值不超过1
      • 左右子树的高度差称为该节点的平衡因子（1,0，-1）
    • 插入
      • 基本思想：首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若不平衡，遭到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点，调整结点位置，是指达到重新平衡
      • 调整方式
        • LL平衡旋转：结点A的左孩子B的左子树插入新结点。即左孩子B代替结点A作为根节点
        • RR平衡旋转：结点A的右孩子C的右子树插入新结点。即右孩子C代替结点A作为根节点
        • LR平衡旋转：结点A的左孩子B的右子树D上插入新结点。即右子树D的根代替B作为A的左孩子，D代替A成为根节点。
        • RL平衡旋转：结点A否右孩子C的左子树E上插入新结点。即左子树E的根代替B作为A的右孩子，E代替A成为根节点
    • 删除
      • 从结点w开始，向上回溯，找到第一个不平衡的结点z
      • 然后对以z为根的子树进行平衡调整，其中x、y和z的情况
        • y是z的左孩子，x是y的左孩子（LL，右单旋转）
        • y是z的左孩子，x是y的右孩子（LR，先左后右双旋转）
        • y是z的右孩子，x是y的右孩子（RR，左单旋转）
        • y是z的右孩子，x是y的左孩子（RL，先右后左双旋转）
      • 与插入操作的调整不同，要先对以z为根的子树进行平衡调整，之后再对其祖先结点进行调整，甚至回溯到根节点
    • 查找
      • 与二叉排序树的相同，在查找过程中，与给定值进行比较的关键字个数不超过树的深度
      • 平均查找长度
  • B树
    • 定义：又称为多路平衡查找树，所有节点的孩子个数的最大值称为B树的阶
    • 性质
      • 结点的关键字（[m/2]-1 , m-1）m为阶数
      • 结点的子树（m/2 , m）
      • 若根节点不是非终端结点，则至少有两棵子树
      • 所有的叶节点都在同一层次上，并且不带信息
      • 所有结点的平衡因子等于0的多路平衡查找树
    • 高度
      • 不包括最后的不带任何信息的叶节点所在的那一层
    • 查找
      • 进行查找与二叉查找树很相似
      • 在B树上查找到某个结点后，先在有序表中进行查找，若查找成功返回，不成功到对应子树中取查找
    • 插入
      • 定位，位置一定是最低层中的某个非叶节点
      • 插入，每个非失败结点的关键字个数都在区间（[m/2]-1 , m-1）。插入后的结点关键字个数小于m，可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于m-1时，必须对结点进行分裂
      • 分裂方法：取一个新结点，在插入key后的原结点，从中间位置[m/2]将其中的关键字，分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置[m/2]的结点插入原结点的父结点。
    • 删除
      • 由于删除后关键字的个数可能会小于[m/2]-1，就需要对结点进行合并
      • 两种情况
        • 兄弟够借，与此结点相邻的右或左兄弟结点的关键字个数大于m/2，就需要调整该结点右或左兄弟结点及其双亲结点达到新的平衡
        • 兄弟不够借，将关键字删除后与右或左兄弟结点及双亲结点中的关键字进行合并
      • 在进行合并的过程当中，双亲结点中的关键字个数会减1，若其双亲结点是根节点且关键字个数减少至0，则直接将根节点删除，合并后的新结点成为根；若双亲结点不是根节点，且关键字个数减少到[m/2]-2，则又要与他们自己的兄弟结点进行调整或合并操作
  • B+树
    • 性质
      • 结点关键字（m/2 , m)
      • 结点子树（m/2 , m）
      • 结点的子树个数与关键字个数相等
      • 所有叶节点包含全部关键字及指向相应记录的指针
      • 所有分支节点中仅包含它的各个子节点中关键字的最大值及指向其子结点的指针
    • 与B树的差异
      • B+树有n个关键字结点含有n棵子树 B树中n个关键字n+1棵子树
      • B+树中关键字个数n（m/2 , m)，B树中（[m/2]-1 , m-1）
      • B+树中，叶结点包含信息，非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址
      • B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中B树中叶结点包含的关键字和其他结点包含的关键字是不重复的
    • B+树每次查找都是一条从根节点到叶结点的路径，不论成功与否
• 哈希表
  • 基本概念
    • 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数
    • 冲突
      • 把两个或两个以上的不同关键字映射到同一地址，发生碰撞的不同关键字称为同义词
      • 设计好的散列函数尽量减少这样的冲突
      • 这样的冲突是不可避免的，还要设计好处理冲突的方法
    • 散列表：根据关键字而直接进行访问的数据结构，建立了关键字和存储地址之间的一种直接映射关系
  • 构造方法
    • 注意
      • 散列函数的定义域必须包含全部需要存储的关键字，值域的范围则依赖于散列表的大小或地址范围
      • 散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生
      • 散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址
    • 直接定址
      • 这种方法计算简单，且不会产生冲突，适合关键字分布基本连续的情况。若关键字分布不连续，空位较多，会造成存储空间的浪费。
    • 除留余数
      • 散列表表长m，取一个不大于m但最接近或等于m的素数p，
      • 该方法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间的任一地址，从而尽可能减少冲突的可能性
    • 数字分析
      • 选取关键字中数码分析较均匀的若干位作为散列地址
      • 这种方法适合于一直的关键字集合，更换了关键字，就要重新构造新的散列函数
    • 平方取中
      • 取关键字的平方值的中间几位作为散列地址，具体多少位要视实际情况而定
      • 这种方法得到的散列地址与关键字的每位都有关系，使散列地址分布比价均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需位数
  • 处理冲突方法
    • 开放定址法
      • 指可存放新表项的空闲地址既向它的同义词表项卡房，又向它的非同义词表项开放，递推公式
      • di增量序列四种取法
        • 线性探测法
          • 冲突发生时，顺序查看表中下一个单元，直到找到一个空闲单元或查遍全表
          • 这种方法可能会造成大量元素在相邻的散列地址上堆积，从而降低查找效率
        • 平方探测法
          • 这种方法可以较好的解决冲突，避免堆积情况的出现
          • 缺点：不能探测到散列表上的所有单元，但至少能探测到一半单元
        • 双散列法
          • 这种方法需要使用两个散列函数，通过第一个散列函数H(key)得到的地址发生冲突时，利用第二个散列函数Hash2(key)计算该关键字的地址增量
          • 在再散列法中，最多经过m-1次探测就会遍历表中所有位置，回到H0位置
        • 伪随机序列
          • 当di=伪随机数序列时，称为伪随机序列法
      • 不能够随便删除表中已有的元素，若删除元素，则会截断其他具有相同散列地址的元素的查找地址。要删除元素时，给他做一个删除标记，进行逻辑删除；缺陷：在进行多次删除后，有许多看似满实则空缺的位置，因此需要定期维护，要把删除标记的元素物理删除
    • 拉链法（连接法）
      • 将所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识
      • 查找、插入和删除操作主要在同一词链中进行
      • 该方法适用于经常进行插入和删除的情况
  • 查找和性能分析
    • 查找步骤
      • 初始化：
      • 检测记录Addr是否在表中存在。若不存在，返回查找失败；若有记录，比较它与key的值，相等，则返回查找成功，否则执行第二步
      • 用给定的冲突处理方法计算"下一个散列地址"，并把Addr置为此地址，转到上一步
    • 性能
      • 散列表在关键字与记录的存储位置之间建立了直接镜像，但是由于"冲突"的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此仍需以平均查找长度作为衡量散列表查找效率的度量
      • 取决于
        • 装填因子
          • 定义为一个表的装满程度
          • 平均查找长度依赖于散列表的装填因子，而不依赖与n ,m
          • 装填因子越大，装填的记录越"满"，发生冲突的可能性越大
        • 散列函数
        • 处理冲突

排序

• 基本概念
  • 排序：重新排列表中的元素，使表中的元素按关键字有序的过程
  • 输入：n个记录R1,R2...Rn，对应的关键字k1,k2....kn
  • 输出：输入序列的一个重排R1',R2',...Rn'，使k1'<k2'<....<kn'
  • 算法稳定性
    • 若待排序表中原有的两个相等的数，在排序完成后这两个关键字顺序不变
    • 算法的稳定性并不能衡量一个算法的稳定性，主要是对算法的性质进行描述
  • 分类
    • 内部排序
      • 排序期间元素全部存放在内存中
      • 比较：通过比较两个关键字的大小确定元素的前后关系
      • 移动：通过移动元素已达到有序
      • 性能取决于算法的时间复杂度(比较和移动)和空间复杂度
    • 外部排序
      • 排序期间元素无法全部同时存放在内存中，元素要在主存和外存之间移动
• 插入排序
  • 是一种简单直观的排序方法，每次将一个待排序的记录按其关键字大小插入前面已排好的子序列，直到全部记录插入完成
  • 直接插入排序
    • 过程
      • 查找出L(i)在L[1...i-1]中的插入位置k
      • 将L[k...i-1]中的所有元素依此后移一个位置
      • 将L(i)复制到L(k)
    • 性能分析
      • 空间复杂度O(1)
      • 时间复杂度
        • 最好：元素已经有序，插入只需比较一次不用移动元素O(n)
        • 平均：总的比较合适移动次数
        • 最坏：排列正好逆序，比较移动次数分别为
        • 总体时间复杂度为
      • 稳定性：从后向前比较再移动，不会出现元素相对位置发生变化的情况，稳定排序方法
      • 适用性：顺序存储和链式存储
  • 折半插入排序
    • 将比较和操作分离，先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。
    • 性能分析
      • 时间复杂度
        • 比较次数与待排序的初始状态无关，表中元素个数有关减少了比较元素的次数为
        • 移动次数没有发生改变，依赖于待排序表的初始状态
        • 总体时间复杂度为
      • 适用性：数据量不大的顺序存储线性表
      • 稳定性：是一个稳定的排序方法
  • 希尔排序
    • 基本思想：将待排序表分成若干个特殊的字表，形如L[i,i+d,i+2d,...,i+ik]，将相隔某个"增量"的记录形成一个字表，对各个字表分别进行直接插入排序，当表中元素基本有序时，再对整体的记录进行一次直接插入排序
    • 过程：取一个小于n的步长d1，把表中全部记录分成d1组，所有距离为d1的倍数的记录放在同一组，在各组内进行直接插入排序，然后取第二个步长d2<d1，然后重复上述过程，直到di=1，此时所有记录在同一组中，再直接插入排序
    • 性能分析
      • 空间复杂度O(1)
      • 时间复杂度
        • 依赖于增量序列的函数
        • n在某个特定的范围时间复杂度为
        • 最坏情况的时间复杂度
      • 稳定性：当相同关键字的记录被划分到不同的字表时，可能会改变他们的相对次序，是一种不稳定的排序算法
      • 仅适用于线性表为顺序存储的情况
• 交换排序
  • 交换：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置
  • 冒泡排序
    • 基本思想：从后往前(或从前往后)两两比较相邻元素的值，若为逆序，交换位置，直到序列比完，结果将最小或最大的元素放到最终位置上，最多n-1趟冒泡就能够把所有元素排好序
    • 性能分析
      • 空间复杂度O(1)
      • 时间复杂度
        • 比较次数
        • 移动次数
        • 平均时间复杂度
      • 稳定性：由于i>j且A[i]=A[j]时，不会发生交换，是一种稳定的排序方法
      • 所产生的的有序子序列是全局有序的，每一趟排序都会将一个元素放到最终位置上
  • 快速排序
    • 基本思想：在待排序表中任取一个元素pivot作为枢轴，通过一趟排序将带排序表划分为独立的两部分，并将pivot放在其最终位置，在其左侧的元素均小于它，右侧的元素都大于它，为一趟快速排序，重复此过程，直至每个子表只有一个元素
    • 性能分析
      • 空间效率
        • 快速排序是递归的，需要借助一个递归工作栈保存每层递归调用的必要信息
        • 最好
        • 最坏O(n)
        • 平均
      • 时间效率
        • 最坏
        • 最好
      • 是所有内部排序算法中平均性能最优的算法
      • 稳定性：若在右端区间有两个关键字相同，且小于基准值，在交换到左端区间会使其相对位置发生改变，是一种不稳定的排序方法
      • 在排序过程中，不产生有序子序列，但是每趟排序后会将基准元素放到其最终位置
• 选择排序
  • 每一趟在n-i+1个待排元素中选取关键字最小的元素，最优有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下一个
  • 简单选择排序
    • 基本思想：排序表为L[1...n]，第i趟排序即从L[i...n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，经过n-1趟就可以使整个排序表有序
    • 性能分析
      • 空间效率O(1)
      • 时间复杂度
      • 稳定性：是一种不稳定的排序方法
  • 堆排序
    • 堆定义：满足L(i)>=L(2i)且L(i)>=L(2i+1) --大根堆 或L(i)<=L(2i)且L(i)<=L(2i+1)--小根堆
    • 排序思路：将存放在L[1...n]中的n个元素简称初始堆，以大根堆为例，堆顶元素为最大值，输出堆顶元素后，将堆底元素送入堆顶，此时根节点不满足大根堆的性质，将堆顶元素向下调整，再输出堆顶元素，直到堆中只剩一个元素
    • 关键：构造初始堆。n个结点的完全二叉树，最后一个结点是第[n/2]个结点的孩子。对第[n/2]个结点为根的子树筛选，使该子树成为堆，之后依此向前进行筛选
    • 性能分析
      • 空间复杂度O(1)
      • 时间复杂度
      • 稳定性：是一种不稳定的排序方法
      • 适合关键字较多的情况
• 归并排序
  • 基本思想：将两个或两个以上的有序表组合成一个新的有序表，假定待排序表中含有n各记录，可将其视为n个有序的字表，每个子表长度为1，然后两两归并，直到合并成一个长度为n的有序表为止
  • 性能分析
    • 空间复杂度O(n)
    • 时间复杂度
    • 稳定性：是一种稳定的排序方法
    • 对N个元素进行k路归并排序时，排序趟数m满足
• 基数排序
  • 是一种不基于比较和移动进行排序的方法，而是对关键字的各位的大小进行排序
  • 实现方法
    • 最高位优先：按关键字为权重递减一次逐层划分成若干个更小的子序列，最后将其进行连接
    • 最低位优先：按关键字权重递增的顺序进行排序，最后形成一个有序队列
  • 性能分析
    • 空间复杂度O(r) r：所用队列的数量
    • 时间复杂度：d趟分配和收集，一趟分配O(n)，一趟收集O(r)，
    • 稳定性：是一种稳定的排序算法
• 性能分析和应用
  • 算法选择
    • n较小，直接插入或简单选择，记录本身信息量较大，简单选择较好
    • 初始状态关键字基本有序：直接插入或冒泡
    • n较大：快速排序(平均时间最短)、堆排序(辅助空间少)和归并排序(算法稳定)
    • 文件的n个关键字随机分布时，借助"比较"的排序算法，至少需要
    • n很大，记录关键字位数较少且可以分解，使用基数排序
    • 记录本身信息量较大，为避免耗费大量时间移动记录，可用链表作为存储结构