408CSFamily/docs/mark-map/ds-map.md

---
title: 数据结构
permalink: /mark-map/ds-map.html
levels: 3
---

# 数据结构

```mindmap
root(数据结构)
    (基础入门)
    (线性表)
    (栈和队列)
    (队列)
    (串)
    (树与二叉树)
    (图论)
    (查找)
    (排序)
```

<a href="../../mind-map/ds-map.html" target="_blank">在线预览</a>

## 基础入门

### 基本概念

- 数据

  - 信息的载体
  - 客观事物属性的数、字符以及所有能够输入到计算机包中并且被计算机程序识别和处理的集合

- 数据元素

  - 数据的基本单位
  - 一个数据元素由若干个数据项组成
  - 数据项是构成数组元素的最小单位，且不可分割

- 数据对象

  - 具有相同性质的数据元素的集合
  - 数据的子集

- 数据类型

  - 原子类型：不可再分的数据类型
  - 结构类型：可以分解成若干分量（成分）的数据类型
  - 抽象数据类型：抽象出具组织和其相关的操作

- 抽象数据类型（ADT）

  - 定义：一个数学模型以及定义在该模型上的一组操作
  - 特点：与计算机内部如何表示和实现是没有关系
  - 作用：数据封装和信息隐藏，让实现与使用相分离
  - 注意：不论内部结构如何变化，只要其数学特性不变，就不会影响到外部的使用

### 数据结构（三要素）

- 逻辑结构

  - 线性结构：线性表、栈、队列、串、数组...
  - 非线性结构：树、图、集合...
  - 集合：除了“同属于一个集合”的关系外，别无其他关系。
  - 线性结构：只存在一对一的关系。
  - 树形结构：存在一对多的关系。
  - 图状结构和网状结构：存在多对多的关系。

- 存储（物理）结构

  - 顺序存储

    - 逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，元素之间的关系由存储单元的邻接关系来体现
    - 优点

      - 可以实现随机存取
      - 元素占用最少的存储空间

    - 缺点

      - 只能使用相邻的一整块存储单元，依赖于物理结构相邻
      - 容易产生外部碎片

  - 链式存储

    - 与顺序存储不同，链式存储不要求逻辑上相邻的元素在物理位置上也相邻
    - 优点

      - 不会出现碎片现象
      - 充分利用所有存储单元

    - 缺点

      - 除了存储元素外，还需要额外存储指针，会占用额外的存储空间（结合数据库索引学习）
      - 链式存储，只能实现顺序存取，不能实现随机存取（指针的遍历）

  - 索引存储

    - 存放数据元素和元素间关系的存储方式，在存储元素信息的同时，还需要建立附加的索引表
    - 优点

      - 检索快（就好比字典有了目录，查询就很快了）

    - 缺点

      - 增加了索引表，占用较多的存储空间（典型的空间换时间策略）
      - 增加、删除数据时，需要对应修改索引表，花费更多时间

  - 散列（Hash）存储

    - 根据元素的关键字直接通过散列（Hash）函数计算出元素的存储地址。
    - 优点

      - 检索快
      - 添加、删除元素结点操作快（获取元素地址直接，整体时间就少了）

    - 缺点

      - 非常依赖于散列函数
      - 会出现散列冲突（主要依赖与散列函数，散列函数不好就很容易出现散列冲突）
      - 出现散列冲突时，解决冲突就会增加时间和空间上的开销

- 数据的运算

  - 运算的定义：针对逻辑结构，指出运算的功能
  - 运算的实现：针对存储结构，指出运算的具体操作步骤

### 算法与算法评价

- 算法

  - 定义

    - 对特定问题求解步骤的一种描述
    - 是指令的有序集合
    - 每一条指令表示一个或多个操作

  - 五大特性

    - 有穷性：执行有穷步后结束、在有穷时间内完成
    - 确定性：每条指令的含义明确，不会产生二义性，对相同的输入只能得出相同的结果
    - 可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的
    - 输入：有零个或者多个输入，输入取决于某个特定的对象的集合
    - 输出：有一个或者多个输出，输出是和输入有着某种特定关系的量

  - 好算法追求的目标

    - 正确性：需要正确的解决求解问题
    - 可读性：便于理解
    - 健壮性：在输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名奇妙的输出结果
    - 效率与低存储量需求

      - 效率：算法执行的时间--->时间复杂度
      - 存储量需求：算法那执行过程中所有要的最大存储空间--->空间复杂度

- 算法的评价

  - 程序语句频度：程序语句在算法中被重复执行的次数
  - 时间复杂度O(n)

    - 最坏空间复杂度：最坏情况下，算法的时间复杂度
    - 平均空间复杂度：所有可能输入实例在同等概率出现的情况下，算法的期望运行时间
    - 最好空间复杂度：最好的情况下，算法的时间复杂度

  - 空间复杂度S(n)

    - 用来定义算法运行过程中需要耗费的存储空间
    - 渐进空间复杂度也被称为空间复杂度
      记作：S(n)=O(g(n))

## 线性表

### 定义和基本操作

- 基本概念

  - 定义：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列
  - 逻辑特性

    - 除表头元素外，线性表中每个元素有且仅有一个
    - 除表尾元素外，线性表中每个元素有且仅有一个直接后继

  - 基本特点

    - 元素个数有限
    - 逻辑上具有顺序性
    - 每个元素都是单个元素
    - 数据类型都相同，元素存储空间大小一致
    - 元素具有抽象性，只讨论逻辑关系

- 基本操作

  - InitList(&L)： 初始化表。构造空的线性表
  - Length(L)：获取表的长度。返回线性表L的长度，即表中的数据元素个数
  - LocateElem(L,e)：按值查找操作。在表L中国查找具有给定关键字的元素
  - GetElem(L,i)：按位查找操作。获取表中第i个位置的元素的值
  - ListInsert(&L,i,e)：插入操作。在表的第i个位置上插入指定元素e
  - ListDelete(&L,i,&e)：删除操作。删除表中第i个位置的元素，并用e返回删除元素的值
  - PrintList(L)：输出操作。按照前后顺序（如：1、2....n）输出线性表的所有元素值
  - Empty(L)：判空操作。当表L为空，则返回true，否则返回false
  - DestoryList(&L)：销毁操作。将线性表销毁，释放线性表L所占用的内存空间

### 顺序表示

- 基础概念

  - 定义

    - 顺序表：顺序存储的线性表
    - 顺序表中的元素的逻辑顺序与实际的物理位置相同
    - 线性表中的元素的位序是从1开始的，数组中的元素的下标是从0开始的

  - 存储分配

    - 静态分配：数组的大小和空间都是实现确定好的，一旦存储空间占满就会产生溢出，直接导致程序崩溃
    - 动态分配：存储数据的空间在程序执行过程中通过动态存储分配语句分配的，即便是数据空间占满，也可以另外开辟一块更大的空间，来替换原来的存储空间
    - malloc()函数： 指针型函数，返回的指针指向该分配域的开头的位置。作用是在内存的动态存储区中分配一个长度为size的连续空间
    - 动态分配不是链式存储，而是属于顺序存储结构，动态分配的物理结构没有改变，依然是随机存取的方式。只是分配的空间大小可以在运行时决定

  - 重要特点

    - 随机访问【重要】
    - 存储密度高
    - 逻辑上相邻的元素物理上也相邻

- 基本操作

  - 插入元素

    - 在顺序表L的第i（1≤i≤L.length+1）个位置插入新元素，成功返回true,失败返回false
    - 时间复杂度

      - 最好情况：在表尾插入，元素向后移动循环没有执行，时间复杂度O(1);
      - 最坏情况：在表头插入，元素后移循环执行n次，时间复杂度为O(n);
      - 平均情况：随机插入，平均次数为：n/2，对应的平均复杂度为O(n);

    - 平均时间复杂度为：O(n)

  - 删除元素

    - 删除顺序表L中第i（1≤i≤L.length+1）个位置的元素。成功则返回true,将被删除的元素用引用变量返回，失败则返回false
    - 时间复杂度

      - 最好情况：删除表尾元素，不需要移动任何元素，时间复杂度为O(1)；
      - 最坏情况：删除表头元素，需要移动除第一个元素外的所有元素，时间复杂度为O(n)
      - 平均情况：随机删除，平均需要(n-1)/2，对应的时间复杂度为O(n)

    - 平均时间复杂度为O(n)

  - 按值查找（顺序查找）

    - 在顺序表L中查找第一个元素值等于e的元素查找成功返回该元素位序（不是角标），查找失败返回0
    - 位序（个人理解）：元素在线性表中的位置序号，角标为i（角标从0开始）,对应的位序为i+1（位序从1开始）。当返回为0时，则直接代表没有命中
    - 时间复杂度

      - 最好情况：查找的元素在表头，只需要比较一次，循环成本最小，时间复杂度为O(1);
      - 最坏情况：查找的元素在表尾或者不存在，需要完整遍历，比较n次，时间复杂度为O(n);
      - 平均情况：随机查找表上的第i个（1≤i≤L.length）元素,平均次数为(n+1)/2,对应时间复杂度为O(n)

    - 平均时间复杂度为O(n)

### 链式表示

- 基础理解

  - 链式存储线性表时，不需要使用连续的存储单元，不要求逻辑上相邻的两个元素在物理位置上也相邻
  - 链式存储线性表时，对线性表的插入、删除元素是不需要移动元素的，只是需要修改指针
  - 理解“链”的含义，链条--->捆绑、指向------>指针

- 单链表

  - 定义：线性表的链式存储称作单链表，通过一组任意的存储单元来存储线性表中的数据元素。
  - 每个链表结点（node）除了存放元素自身的信息外，还需要存放一个指向其后继结点的指针。通过指针建立起链表元素之间的线性关系
  - 单链表可以解决顺序表需要大量连续存储空间的缺点，但是单链表在数据域的基础上附加了指针域，存在浪费存储空间的缺点
  - 单链表的元素是离散地分布在存储空间中的，不能直接找到表中特定的结点，需要从头开始遍历、一次查找【单链表是非随机存取的存储结构】
  - 头结点相关

    - 定义：为了操作上的方便，在单链表第一个结点之前附加一个结点，叫做头结点。
    - 基本特点

      - 不论单链表是否带头结点【可选】，头指针始终指向链表的第一个结点
      - 头结点的指针域指向线性表的第一个元素结点
      - 头结点的数据域可以不存任何信息、也可以记录表长等基础信息
      - 头结点是带头结点的链表中的第一个结点

    - 优点

      - 因为开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，不需要进行特殊处理
      - 无论链表是否为空，头指针始终是指向头结点的头结点的非空指针
      - 头结点的引入，很好的统一了空表和非空表的操作，有效避免头指针空指针异常问题

  - 基本操作

    - 链表创建

      - 头插法

        - 定义：从空表开始，生成新的结点，将读取的数据存放在新结点的数据域中，将新结点插入到当前链表的表头【头结点之后】
        - 读入数据的顺序与生成的链表中的元素顺序是相反的
        - 每个结点插入的时间复杂度为O(1),单链表长度为n时，头插法的时间复杂度为O(n)

      - 尾插法

        - 定义：新结点插入到当前链表的表尾上，必须增加一个尾指针r,始终指向当前链表的尾结点
        - 读入数据的顺序与生成的链表中的元素顺序完全一致
        - 每个结点插入的时间复杂度为O(1),单链表长度为n时，尾巴插法的时间复杂度为O(n)
        - 相比头插法附设了一个指向表尾结点的指针，但时间复杂度与头插法相同

    - 按序号查找

      - 定义：在单链表中从第一个结点出发，顺指针next域逐个往下搜索、遍历，直到找出第i个结点为止，否则返回最后一个结点指针域NULL
      - 时间复杂度为：O(n)

    - 按值查找

      - 定义：从单链表的第一个结点开始，从前往后依次比较表中个结点数据域的值，等于给定值e，则返回该结点的指针；若整个单链表【遍历完】中没有数据域值为e的结点，则返回NULL；
      - 时间复杂度为：O(n)

    - 插入结点

      - 定义：单链表中，将值为x的新结点插入到单链表的第i个位置上
      - 基本步骤

        - 第一步： 检查插入位置的合法性；
        - 第二步： 找到待插入位置的前驱结点，即第（i-1）个结点；
        - 第三部： 在前驱结点后插入新结点；
        - 过程不能更换，避免后继指针不存在的问题

      - 时间复杂度

        - 插入结点的时间复杂度集中在查找第(i-1)个元素，时间复杂度为O(n)
        - 如果在给定结点的后面插入新结点，只需要执行p->next=s操作，时间复杂度为O(1)

      - 前插操作：在某结点的前面插入一个新的结点
      - 后插操作：在某结点的后面插入一个新的结点，单链表插入算法中，通常采用后插操作的
      - 对结点的前插操作都可以转化为后插操作，前提：需要从单链表的头结点开始顺序查找到其前驱结点；时间复杂度为O(n)。

    - 删除结点

      - 定义：将单链表L的第i个结点元素删除；
      - 基本步骤

        - 第一步： 先检查删除位置的合法性；
        - 第二步： 查找表中的第（i-1）个结点，即被删结点的前驱结点；
        - 第三步： 移动指针，删除结点元素；

      - 和插入算法一样，时间都消耗在查询前驱结点上，时间复杂度为：O(n)
      - 利用p结点的后继结点将p结点删除【经典思路】

        - 第一步：申请结点q，使其只想p结点的后继结点；
        - 第二步：将p结点的数据域值换成其后继结点的数据域；【注意，交换没什么意义，最终p的后继结点会删除、释放】
        - 第三步：p的指针域指向q的指针域，q结点从链中“断开”
        - 第四步：释放q的内存空间
        - 相比按值查找前驱结点来删除给定的结点p，利用后继结点来删除的时间复杂度更小，为：O(1)

    - 计算表长(遍历)

      - 定义：计算单链表中数据结点（不含头结点）的个数
      - 算法思路：从第一个结点开始顺序依次访问表中的每一个结点，为此需要设置一个`计数器变量`，每访问一个结点，计算器加1，直到访问到空结点为止。
      - 时间复杂度：O(n)
      - 判空条件

        - 不带头结点的单链表L为空,判定条件是L=NULL。
        - 带头结点的单链表L为空，判空条件：L->next=NULL

- 双链表

  - 定义：在单链表的结点中增加了一个指向结点前驱的`prior`指针，由prior指针域、data数据域、next指针域三部分组成。
  - 基本特点

    - 双链表仅仅在单链表的结点中增加了一个指向结点前驱的prior指针
    - 按值查找、按序号查找在单链表和双链表上的操作是相同的
    - 和单链表不同，插入、删除操作除了修改next指针域，双链表还需要修改prior指针域，确保不断`链`【重要】

  - 基本操作

    - 插入结点

      - 第一步：s->next=p->next
      - 第二步：p->next-prior=s
      - 第三步：s->prior=p
      - 第四步：p->next=s
      - 时间复杂度：O(1)
      - 注意：结点p和s的前驱、后继指针要关联清楚，第一二步必须在第四步之前完成【重要】

    - 删除结点

      - 第一步：p->next=q->next
      - 第二步：q->next->prior=p
      - 第三步：free(q) 释放结点内存空间
      - 时间复杂度：O(1)
      - 注意：删除双链表结点p的后继结点的第一二步，顺序可换，及时释放内存空间【重要】

- 循环链表

  - 循环单链表

    - 定义：在单链表的基础上，将最后一个结点（尾结点）的指针由`NULL`改为指向`头结点`，形成`环`。【单链表----->循环单链表】
    - 判断条件

      - 不是判断头结点的指针是否为空，而是需要判断是否等于头指针
      - 表为空时，头结点的next指针域其实是指向自己
      - 结点的next指针指向自己，也就能判断表为空

    - 基本特点

      - 在循环单链表中，尾结点\*p的next指针域指向链表L（即：头结点），形成了`闭环`,不存在指针域为`NULL`的结点
      - 由于循环单链表是个`环`,在任何位置上的插入、删除操作都是等价的，不需要去判断是否是表尾
      - 单链表只能从头结点（表头结点）开始往后顺序遍历整个表，循环单链表可以从表中任意位置开始遍历整个链表，结点是等价的
      - 循环单链表可以抽象为时钟，形成的`环`是有顺序的
      - 频繁的`表头`和`表尾`操作，可以对循环单链表设置`尾指针`，而不设置`头指针`，明确尾指针r后，头指针即为：`r->next` ，减少头指针到尾指针间的遍历，时间复杂度:O(n)---->O(1)

  - 循环双链表

    - 定义：在双链表的基础上，将尾结点的next指针指向头结点，将头结点的prior指针指向尾结点。【双链表----->循环双链表】
    - 判空条件

      - 循环双链表为空时，头结点\*p的prior指针和next指针都指向L
      - 同时满足

        - p->prior=L
        - p->next=L

    - 基本特点：从双向链表中的任意一个结点开始，都可以很方便地访问它的`前驱结点`和`后继结点`

- 静态链表

  - 定义：借助数组来描述线性表的链式存储结构，结点元素同样存在数据域`data`和指针域`next`
  - 需要注意

    - 和普通的链表的指针域不同的是，静态链表的指针是结点元素的相对地址(数组下标)，也称为`游标`，建议结合高级语言中数组的概念来理解；
    - 与顺序表一样，虽然静态链表属于链表，但是存储时需要预先分配一块连续的内存空间
    - 静态链表是通过`数组游标`来访问下一个结点元素

  - 特点

    - 静态链表以`next=-1`作为结束的标志【尾结点】
    - 和动态链表相同，插入、删除操作不需要移动元素，只需要修改指针；
    - 总体来说，静态链表没有单链表使用方便，需要将整个链表存储在一块连续的内存空间中，内部的存储可以分散，通过指针构成`链`的关系

- 零碎知识补充

  - 无论是链表的插入还是删除操作，必须保证不断链【重要】
  - 顺序存储结构可以随机存取也能顺序存取，链式结构只能进行顺序存取
  - 顺序存储方式同样适合图和树的存储，例如：满二叉树的顺序存储
  - 队列需要在表头删除元素，在表尾插入元素【先进先出】，采用带尾指针的循环单链表比较方便
  - 静态链表中的指针称为`游标`，指示下一个元素在数组中的`下标`
  - 静态链表用数组表示，需要预先分配较大的连续空间，同时具有一般链表的特点（插入、删除元素不需要移动元素）
  - 单链表设置头结点的

    - 目的：方便运算
    - 好处

      - 有头结点后，插入、删除数据元素的算法统一起来了，不需要判断是否在第一个元素之前插入或者删除第一个元素了
      - 不论链表是否为空，头指针是指向头结点的`非空指针`，链表的头指针不变，因此空链表和非空链表的处理也就统一起来了。

### 顺序表和链表的比较

- 存取方式

  - 顺序表支持顺序存取和随机存取
  - 链表只能从表头顺序存取元素，支持顺序存取

- 逻辑结构与物理结构

  - 顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻【一定性】
  - 链式存储时，逻辑上相邻的元素，对应的物理存储位置不一定相邻【可以相邻，也可以不相邻】
  - 链式存储的逻辑关系通过指针链接表示

- 时间复杂度

  - 按值查找

    - 顺序表无序的情况下，顺序表和链表的时间复杂度均为O(n)；
    - 顺序表有序的情况下，顺序表的时间复杂度为O(log2n),链表为O(n)；

  - 按序号查找

    - 顺序表支持随机访问，时间复杂度为O(1)；
    - 顺序表不支持随机访问，时间复杂度为O(n)；

  - 插入、删除

    - 顺序表平均需要移动半个表长的元素；
    - 链表只需要修改相应结点的指针域，不需要移动元素；
    - 链表结点除了数据域，还有指针域，在存储空间上比顺序存储需要更大的存储空间，付出更大的存储代价，存储密度不够大

- 空间分配

  - 顺序存储

    - 静态分配

      - 需要预先分配足够大的存储空间
      - 空间装满后不能扩充，存储新元素将出现`内存溢出`
      - 存储空间过大，顺序表后部闲置空间过多，造成`内部碎片`
      - 存储空间过小，会造成`内存溢出`

    - 动态分配

      - 能够扩充存储空间
      - 需要移动大量元素，操作效率降低
      - 内存中没有更大块的连续存储空间，将会导致空间分配失败；

  - 链式存储

    - 结点空间只在需要的时候申请分配
    - 只要内存由空间就可以分配，操作灵活、高效

### 存储结构选取

- 基于存储的考虑

  - 对线性表的长度和存储规模难以估计时，不宜采用顺序表存储
  - 链表不用事先估计存储规模，但存储密度较低
  - 链式存储结构的存储密度小于1，不要求连续的存储空间

- 基于运算的考虑

  - 随机存取

    - 顺序表支持随机存取，按序号查找顺序表的时间复杂度为O(1)，相对较好
    - 链表不支持随机存取，按序号查找链表的时间复杂度为O(n)

  - 插入、删除操作

    - 顺序表的插入、删除操作，平均需要移动表中一半的元素，当表的数据量较大时，这种情况需要重点考虑的
    - 链表的插入、删除操作，也是需要找插入位置（前驱结点、后继结点），主要的操作还是比较操作，相对较好

- 基于环境的考虑

  - 顺序表容易实现，任何高级语言中都有数组类型
  - 链表操作是基于指针的，指针移动，相对复杂

- 综合结论

  - 通常比较稳定的线性表选择顺序存储
  - 频繁进行插入、删除操作的线性表，应该选择链式存储，动态性较强

## 栈和队列

### 栈【后进先出】

- 基础概念

  - 定义： 只允许在一端进行插入或者删除操作的线性表。

    - 后进先出
    - 明确栈是一种线性表
    - 限定栈只能在某一端进行插入或者删除操作

  - 栈顶：线性表允许进行插入和删除的一端
  - 栈底：不允许进行插入和删除的另外一端，是固定的
  - 空栈：不含任何元素的空表，也叫栈空

- 基本操作

  - InitStack(&S): 初始化一个空栈S，栈顶指针初始化为-1
  - StackEmpty(S): 判断一个栈是否为空，如果栈空则返回true,否则返回false
  - Push(&S,x): 进栈，若栈未满，x进栈操作，插入到栈内成为新的栈顶元素
  - Pop(&S,&x): 出栈，若栈非空，出栈操作，弹出栈顶元素，用指针x进行返回
  - GetTop(S,&x): 读栈顶元素，若栈S非空，用x返回栈顶元素
  - ClearStack(&S): 销毁栈，释放栈S占用的存储空间

- 顺序存储结构

  - 顺序栈

    - 定义：栈的顺序存储，利用一组地址连续的存储单元存放自栈底到栈顶的所有元素，同时**附加一个用来指向当前栈顶位置的指针**
    - 顺序栈S【重要，栈顶指针初始化为-1】

      - 栈顶指针S.top

        - 初始时，S.top=-1
        - 栈顶元素:S.data[S.top]

      - 进栈操作：栈不满时，栈顶+1，再进栈
      - 出栈操作：栈非空时，取栈顶元素，栈顶-1
      - 栈满条件：S.top=MaxSize-1
      - 栈空条件：S.top=-1
      - 栈长：S.top+1
      - 当对栈的最大使用空间估计不足时，容易出现栈上溢(外溢)，需要主动向用户报告反馈，避免出现错误；

    - 栈顶指针初始化为0【更多是为-1】

      - 入栈： `S.data[S.top++]=x`
      - 出栈： `x=S.data[--S.top]`
      - 同时， 栈空、栈满条件也会有变化

    - 基本运算

      - `InitStack(&S)`: 初始化一个空栈`S`,栈顶指针初始化为-1
      - `StackEmpty(S)`: 判断一个栈是否为空，即：栈顶指针是否为-1，如果栈空则返回`true`,否则返回`false`
      - `Push(&S,x)`: 进栈，若栈未满，`x`进栈操作，插入到栈内成为`新的栈顶元素`。
      - `Pop(&S,&x)`: 出栈，若栈非空，出栈操作，**弹出栈顶元素**，用指针`x`进行返回。
      - `GetTop(S,&x)`: 读（获取）栈顶元素，若栈`S`非空，用x返回栈顶元素。

  - 共享栈

    - 定义：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个`一维存储空间`，将两个栈的栈底分别设置在共享空间的两端，两个栈顶则向共享空间的中间延伸
    - 基础概念

      - 两个栈（0、1号顺序栈）的栈顶指针都指向栈顶元素
      - 0号栈栈顶指针`top=-1`时，0号栈为空
      - 1号栈栈顶指针`top=MaxSize`时，1号栈为空
      - 当且仅当两个栈的栈顶指针相邻(`top1-top0=1`),可以判断共享栈栈满

    - 进栈【先移动指针，后赋值】

      - 当0号栈进栈时，0号栈栈顶指针top0`先加1后赋值`
      - 当1号栈进栈时，0号栈栈顶指针top1`先减1后赋值`

    - 出栈【先赋值，后移动指针】

      - 当0号栈进栈时，0号栈栈顶指针top0`先赋值后减1`
      - 当1号栈进栈时，0号栈栈顶指针top1`先赋值后加1`

    - 重要特性

      - 共享栈能够更有效的利用存储空间，两个栈空间进行相互调节
      - 只有当这个存储空间（即：共享空间）被占满时才会发生上溢
      - 共享栈对存取效率没有什么影响，存取数据的时间复杂度都为O(1)，在栈顶操作。

- 链式存储结构

  - 基本概念

    - `链栈`： 采用链式存储的栈
    - `栈满`：对于链栈来说，是基于链式存储的，基本不存在栈满的情况，除非内存已经没有使用空间了
    - `栈空`：对于空栈来说，链表原来的定义是头指针指向空，那么链栈的空其实就是`top＝NULL`,链栈元素总数为0
    - 通常对于链栈来说，是不需要头结点的，当然也存在带头结点的链栈

  - 基础操作【基于单链表】

    - 入栈

      - 如果链栈不存在，则栈满，入栈操作失败，返回false;
      - 如果链栈存在，进行单链表的结点插入操作，移动指针，结点元素赋值，再将结点压入链栈中，移动链栈栈顶指针，最后链栈元素总数+1，返回true

    - 出栈

      - 如果链栈不存在，或者为空栈，则无法进行出栈操作，返回false
      - 如果链栈满足出栈条件，则通过栈顶指针获取到链栈栈底结点，将其数据域赋值给变量e，移动栈顶指针指向待出栈元素的后继结点，同时释放待出栈元素的内存空间，链栈元素总数-1 ，出栈成功，返回true.

    - 基于单链表的链栈入栈、出栈操作，时间复杂度都为O(1）【重要】

  - 优点

    - 便于多个栈共享存储空间
    - 不存在栈满上溢的情况，避免程序因溢出导致出错
    - 有效的提高存取效率

### 队列【先进先出】

- 基本概念

  - 队列：和栈一样，是一种操作受限制的线性表,只允许在表的一端进行插入，在表的另外一端进行删除，简称为`队`，常记作：`Queue`
  - 队头：允许进行删除操作的一端，也叫做`队首`，常记作：`Front`
  - 队尾：允许进行插入操作的一端，常记作：`Rear`
  - 空队列：不含任何元素的空表，注意这个表是指`线性表`
  - 入队： 向队列中插入元素，也叫做`进队`
  - 出队： 删除队列元素，也叫做`离队`

- 基础操作

  - InitQueue(&Q)： 初始化一个队列，构造空队列Q
  - `QueueEmpty(Q)`： 判断队列是否为空，队空返回true,否则返回false
  - EnEmpty(&Q,x)： 入队，如果队列Q未满，将x入队，成为新的队尾元素
  - DeEmpty(&Q,&x)： 出队，如果队列Q非空，删除队头元素，复制给x返回
  - GetHead(Q,&x)： 读取队头元素，如果队列Q非空，则将队头元素赋值给x

- 顺序存储

  - 顺序队列

    - 队列的顺序实现是指分配一块连续的存储单元用来存放队列中的元素，并且附加两个指针

      - front指针： 指向队头元素的位置
      - rear指针： 指向队尾元素的位置

    - 初始状态（队空条件）：Q.front===Q.rear===0
    - 入队操作：队不满时，先赋值给队尾元素，再移动队尾指针+1
    - 出队操作： 队不空时，先取队头元素值，再移动队头指针+1
    - Q.front===Q.rear===0,那能用Q.rear==MaxSize来表示队满嘛？【不行】

  - 循环队列

    - 把顺序队列臆想为一个环状的空间，将存储队列元素的表从逻辑上看做为一个环
    - 初始时：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
    - 除法取余运算（%）【解决顺序队列“上溢出”】问题
    - 如何区别队空还是队满？

      - 方案一：牺牲一个单元来区分队空和队满

        - 前提：队头指针在队尾指针在队尾指针的下一个位置作为队满标志【重要】
        - 队满条件：(Q.rear+1)%MaxSize==Q.front
        - 队空条件：Q.front==Q.rear
        - 队列中元素个数：(Q.rear+MaxSize-Q.front)%MaxSize

      - 方案二：类型中增设表示元素个数的数据成员

        - 直接和MaxSize去比较
        - 队空条件： Q.count=0
        - 队满条件： Q.count=MaxSize
        - 【注意】不论是队空还是队满，对会存在Q.front=Q.rear,这个可以通过前面方案一解决

      - 方案三：类型中增设tag数据成员标记

        - 通过添加tag标记的方式，区分队空还是队满
        - tag==0的情况下，如果因为删除导致Q.front==Q.rear，则队空；
        - tag==1的情况下，如果因为插入导致Q.front==Q.rear，则队满；
        - tag的主要作用

          - 在有元素入队的时候，设置tag=1
          - 在有元素出队的时候，设置tag=0

- 链式存储

  - 链队列

    - `链队列`：和顺序队列一样，基于队列的链式表示叫做`链队列`，实际上为：**一个同时带有队头指针和队尾指针的单链表**

      - 头指针指向队头结点
      - 尾指针指向队尾结点（单链表的最后一个结点）

    - 不带头结点链式队列

      - 队空： linkQueue.front==NULL且linkQueue.rear==NULL
      - 出队： 先判断队列是否为空，非空队列则取出队头元素，从链表中闪出去，队头指针Q.front指向下一个结点，如果出队的结此为尾结点，出队后队空，需要将Q.front和Q.rear都置为NULL
      - 入队： 建立一个新的结点，将新的结点插入到链表的尾部，修改队尾指针Q.rear指向新插入的结点。如果原队列为空，需要将队首指针也指向该结点
      - 【入队、出队操作，都需要考虑队空的情况下的特殊处理，不带头结点的队列导致队空队首和队尾指针都为NULL，麻烦】

    - 带头结点的链式队列

      - 【复杂的入队、出队操作就统一起来】
      - 队空：Q.front==Q.rear,都指向头结点，一般数据域可以为空
      - 出队：判断队列是否为空，队列非空则在队首移动指针，将队首指针指向下一个元素。如果队列中就一个元素，则出队后将成为空队，Q.rear==Q.front,最后释放元素内存空间。
      - 入队：将元素插入队尾，移动队尾指针，即便为空队列入队，由于队列带有头结点，此时就很好的避免操作队首指针了。
      - 子主题 5

    - 特别注意

      - 用单链表表示的链式队列非常适合频繁出队、入队、元素变化大的场景
      - 不存在队满情况，也不会出现溢出情况；
      - 链式队列不会出现存储分配不合理、“溢出”的情况，内存动态分配

    - 基本操作【带头结点】

      - 队列初始化
      - 判断队空：Q.front==Q.rear
      - 入队【重要】
      - 出队【重要】

  - 双端队列

    - 允许在两端都可以进行入队和出队操作的队列，元素的逻辑结构仍然是线性结构
    - 双端队列的两端分别称为前端和后端，两端都可以入队和出队

      - 进队：前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列前端进的元素后面;
      - 出队：无论是前端还是后端出队，先出的的元素排列在后出的元素的前面

    - 输入受限的双端队列：允许在一端进行插入和删除操作，但在另外一端只允许进行删除的双端队列
    - 输出受限的双端队列：允许在一端进行插入和删除曹组，但在另外一端只允许进行插入的双端队列

    - 如果限定双端队列从某个断点插入的元素只能从该端点删除，那么此时的双端队列就演变为两个栈底相邻的栈

  - 补充

    - 最适合用来链队的链表是：带队首指针和队尾指针的非循环单链表
    - 栈和队列的逻辑结构都是线性表，存储结构可能是顺序的（顺序栈、顺序队列），也可能是链式的（链栈、链队）
    - 不论是顺序存储还是链式存储，栈和队列都只能进行顺序存取（本质是线性表）。数组是可以做到随机存取（本质是顺序表）
    - 队列先进先出的特性：先进队列的元素先出队列，后进队列的元素后出队列

### 应用

- 【栈】括号匹配
- 【栈】表达式求值
- 【栈】递归算法

  - 定义： 如果在一个函数、过程或数据结构的定义中又应用了自身，那么这个函数、过程或者数据结构称为递归定义的，简称递归。
  - 递归通常把一个大型的复杂问题，层层转化为一个与原问题相似的规模较小的问题来求解
  - 斐波拉切数列算法优化

    - 使用非递归实现
    - 使用空间换效率，例如：数组
    - 使用缓存，存放数据

  - 必须注意递归模型不能是循环定义，
    需要满足两个条件

    - 递归表达式（递归体）
    - 边界条件（递归出口），即：算法结束条件

  - 特点

    - 很大程度上减少了程序的代码量
    - 算法效率不高【重要特点】
    - 调用次数过多容易造成栈溢出

- 【队列】层次遍历
- 【队列】计算机系统

  - 解决主机和外部设备之间速度不匹配的问题
  - 解决由多用户引起的资源竞争问题

### 特殊矩阵的压缩存储

- 在`计算机图形学`、`工程计算`中占有举足轻重的地位。
- 数组定义：由n(n≥1)个相同类型的数据元素构成的有限序列。
- 重要概念

  - 【压缩存储】多个值相同的元素只分配一个存储空间，对零元素不分配存储空间---->节省存储空间。
  - 【特殊矩阵】具有很多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。
  - 【稀疏矩阵】矩阵元素个数s相对于矩阵中非零元素的个数t来说非常多、差距非常大，即`s>>t的矩阵`可以叫`稀疏矩阵`

- 常见的特殊矩阵

  - 对称矩阵
  - 上、下三角矩阵
  - 对角矩阵（带状矩阵）
  - ......

- 注意

  - 常规方法来存储稀疏矩阵，会想当浪费存储空间，所以稀疏矩阵只需要存储非零元素
  - 通常非零元素的分布是没有规律的，除了存储非零元素外，还需要存储元素所在位置的行和列
  - 寻相互存储三元组 `<行标，列表，值>`
  - 三元组的结点存储了行标(row)、列表(col)、值(value)三种信息，是主要用来存储稀疏矩阵的一种数据结构

- 数组和线性表的关系

  - 数组是线性表的推广
  - 数组一旦被定义，维数和维界就不再改变
  - 除了结构的初始化和销毁外，数组只会有存取元素和修改元素的操作

- 数组的存储结构

  - 按行优先
  - 按列优先

## 树与二叉树

### 树

- 定义
- 术语

  - 结点

    - 祖先结点
    - 父子结点
    - 兄弟结点
    - 孩子结点
    - 子孙结点
    - 分支结点
    - 叶子结点（终端结点）

  - 度

    - 结点的度
    - 树的度

  - 结点的深度、高度、层次
  - 有序树和无序树
  - 路径和路径长度
  - 森林

- 性质

### 二叉树

- 定义和特性
- 存储结构
- 二叉树遍历
- 线索二叉树

### 树和森林

- 存储结构
- 树、森林与二叉树转换
- 遍历
- 并查集应用

### 应用

- 二叉排序树
- 平衡二叉树
- 哈夫曼树
- 哈夫曼编码

## 图论

### 定义

### 基本操作

- Adjacent(G,x,y)
- Neighbors(G,x)
- InsertVertex(G,x)
- DeleteVertex(G,x)
- AddEdge(G,x,y)
- RemoveEdge(G,x,y)
- FirstNeighbor(G,x)
- NextNeighbor(G,x,y)
- Get_edge_value(G,x,y)
- Set_edge_value(G,x,y,v)

### 存储及操作

- 邻接矩阵法
- 邻接链表法
- 十字链表
- 邻接多重表

### 图的遍历

- 广度优先搜索（BFS）
- 深度优先搜索（DFS）
- 连通性

### 图的应用

- 最小生成树（MST）
- 最短路径
- 拓扑排序
- 关键路劲

## 查找

### 基本概念

- 查找：在数据集合中寻找满足某种条件的数据元素的过程
- 查找表（查找结构）：用于查找的数据集合

  - 数据元素（记录）的类型相同
  - 可以是一个数组或者链表等数据类型
  - 常见操作

    - 查询某个特定元素是否存在
    - 检索满足条件的特定元素的各种属性
    - 数据元素插入
    - 数据元素删除

- 静态查找表：不需要动态地修改查找表，与动态查找表对应

  - 顺序查找
  - 折半查找
  - 散列查找
  - ....

- 动态查找表：需要动态地插入或者删除的查找表

  - 二叉排序树的查找
  - 散列查找
  - ....

- 关键字：数据元素中唯一标识该元素的某个数据项的值

  - 使用关键字查找，查找结果应该是【唯一的】
  - 可以类比集合中不重复的key
  - 是不是想起了数据库的主键的概念？？？？

- 平均查找长度：所有查找过程中进行关键字的比较次数的平均值

  - 查找长度：一次查找需要比较的关键字次数
  - 【是衡量查找算法效率的最主要的指标】

### 顺序查找（线性查找）

- 主要用于在线性表中进行查找

  - 一般的【无序线性表】的顺序查找
  - 按关键字【有序的顺序表】的顺序查找
  - Tips：顺序表是指顺序存储的线性表，前面的有序才强调元素有序，顺序强调的是存储方式

- 基于一般线性表的顺序查找

  - 最直观的查找方式
  - 基本思想：从线性表的一端开始，逐个查询条件和关键字进行比对即可
  - 【重要】：哨兵的引入，可以避免很多不必要的判断语句，提高程序的效率
  - 平均查找长度

    - 查找成功

      - 第i个元素需要进行(n-i+1)次关键字比较
      - 概率相等的情况下：(n+1)/2

    - 查找失败【没有找到元素】

      - 各关键字比较次数：(n+1)
      - 平均查找长度：(n+1)

  - 综合分析

    - 【缺点】：n较大时，平均查找长度较大，效率低
    - 【优点】：对数据元素的存储没有要求，顺序存储和链式存储都可行。对数据元素的有序性也没有要求
    - 【注意】：线性的链表只能进行顺序查找

  - 通常情况下，查找表中记录的查找概率并不相等

- 基于有序表的顺序查找

  - 预先已经知道表是按照关键字有序的，基于【二叉判定树】来查找，不用全部遍历----->【降低顺序查找失败的平均查找长度】
  - 平均查找长度

    - 查找成功

      - 和一般线性表的顺序查找一样
      - 概率相等的情况下：(n+1)/2

    - 查找失败

      - 到达是失败结点所查找的长度=失败结点父结点所在的层数【建议画画二叉判定树】
      - 查找概率相等时，平均查找长度:n/2 + n/(n+1)

  - 【注意】：有序表的顺序查找中的线性表可以是链式存储结构的

### 折半查找（二分查找）

- 【注意】仅仅适用于有序的顺序表
- 基本思想：首先与表中间位置元素的关键字比较，相等则查找成功，不相等则向左|向右继续与该部分中间元素比较......
- 核心思路：左右双指针，互相往中间靠拢，可以用二叉判定树来辅助思考
- 平均查找长度【计算非常重要】

  - 查找成功

    - 折半查找法查到给定值的比较次数最多不会超过【判定树】的高度
    - 相等概率下，平均查找长度约等于log2(n+1) -1 ,【建议结合二叉树高度计算来理解】

  - 查找失败直接看例题.....

- 综合分析

  - 折半查找的时间复杂度为O(log2n), 平均情况下笔顺序查找O(n)的效率高
  - 折半查找需要方便地定位查找区域---->存储结构必须具有【随机存取】的特性
  - 【注意】仅仅适用于有序的顺序表，不适用链式存储结构，要求表按关键字有序排列

### 分块查找（索引顺序查找）

- 具备顺序查找和折半查找的优点，既有动态结构，又能适用于快速查找
- 是不是有点【希尔排序】和【直接插入排序、折半插入排序】的发展效果？？？？？
- 基本思想：查找表分成若干个子块

  - 块内元素可以无序，【块之间必须有序】
  - 前一块的最大关键字永远小于后一块的最小关键字
  - 【重要】：建立索引表，包含每个分块额最大关键字和第一个元素的地址（起始角标）
  - 索引表按关键字有序排列

- 查找方式

  - 索引表：顺序查找或者折半查找
  - 块内：顺序查找<----- 块内可以无序

- 【直接看书】平均查找长度=索引查找平均长度+块内查找的平均长度

### 【直接看书|视频，这部分我很迷糊】B树和B+树

- B树（多路平衡查找树）

  - 基础概念

    - 阶：所有结点的孩子结点数的最大值
    - m阶B树（可能为空树）满足

      - 树中每个结点至多有m棵子树（即至多包含m-1个关键字）
      - 如果根结点不是终端结点，至少有两棵子树
      - 所有的叶结点都出现在同一个层次上，不带任何信息
      - ....

    - B树是所有结点的平衡因子均为0的多路查找树

  - 基本操作

    - 高度

      - B树的大部分操作需要的磁盘存取次数和B树的高度成正比
      - B树的高度不包括最后的不带任何信息的叶结点所处的那一层【有的参考书，也包含这部分】
      - 【重要】如果每个结点重点额关键字个数达到最少，则容纳同样多关键字的B树的高度可以达到最大
      - ....

    - 查找

      - 步骤

        - 在B树中找结点【磁盘中进行】
        - 在结点内找关键字【内存中进行】----> 采用【顺序查找法】或【折半查找法】
        - 【Tips】B树常存储在磁盘上，在磁盘上找到目标节点后，将结点中的信息读入到内存

      - 当查找到叶子结点，对应的指针为空指针，即树中没有对应的关键字

    - 插入

      - 插入操作比查找操作复杂多
      - 步骤

        - 定位

          - B树查找算法--->最底层中某个非叶结点
          - 【重要】B树的插入关键字一定是插入到最底层的某个非叶结点内

        - 插入

          - 插入结点关键字个数小于m----> 直接插入
          - 插入后检查插入结点内关键字个数，【大于m-1必须进行分裂】

        - 【直接看书】】注意分裂的方法

    - 删除（删除的关键字在终端结点）

      - 直接删除关键字
      - 兄弟够借
      - 兄弟不够借

- B+树的概念

  - B+树是根据数据库的需要需要的一中B树的变形树
  - m阶的B+树需要满足的条件

    - 每个分支结点最多有m棵子树（子结点）
    - 结点的字树个数与关键字相等
    - 非叶、根结点至少有两棵子树，其他分支结点至少有m/2(向上取整)棵子树
    - 所有叶结点包含全部关键字及指向相应记录的指针

      - 叶结点按关键字大小排列
      - 相邻结点按大小顺序相互链接起来

    - 【反复理解】所有的分支结点（理解为索引的索引）中仅仅包含它的各个子结点（下一级的索引快）中关键字的最大值和指向其子结点的指针
    - ....

### 散列（Hash）表

- 基本概念

  - 散列函数：一个把查找表中的关键字映射成该关键字对应的地址（数组下标、索引、内存地址等）的函数
  - 散列冲突：散列函数把两个或者多个不同关键字映射到同一个地址上，【冲突总是不可避免的】
  - 同义词：发生散列冲突（碰撞）的不同关键字
  - 散列表：根据关键字直接访问的数据结构，是关键字和存储地址之间的一种直接映射关系
  - 理想情况下，散列表中查找时间复杂度为O(1)，与元素个数无关
  - 基于【比较】的查找算法，查找效率取决于比较的次数
  - 以上可以结合哈希加密、布隆过滤器等工作中的编程概念去比对学习....

- 散列函数

  - 构造散列函数，需要注意

    - 散列函数的定义域【必须】要包含全部需要存储的关键字，值域的范围则依赖于散列表的大小或地址范围
    - 散列函数计算出来的地址应该能【等概率、均匀的】分布在整个存储空间，尽可能减少散列冲突---> 【压测】
    - 散列函数应该尽量简单，能够在较短时间内就计算出任一关键字对应的散列地址

  - 常用散列函数

    - 直接定址法

      - 直接去关键字的某个【线性函数值】为散列函数
      - 优点

        - 计算简单
        - 【不会产生冲突】
        - 适合关键字的分布【基本连续】的情况

      - 缺点：关键字分布不连续时，空位较多，将造成存储空间的浪费

    - 除留余数法

      - 最简单、最常用的散列方法
      - 关键在于【选择被除数P】，等概率进行映射，尽可能减少冲突的可能性

    - 数字分析法

      - 适用于已知的关键字集合
      - 如果更换了关键字，就需要重新构造新的散列函数

    - 平方取中法

      - 取关键字的平方值的中间几位来作为散列地址
      - 适用于关键字的每一位取值都不够均匀或小于散列地址所需要的位数

    - 折叠法

      - 将关键字分割成位数相同的几部分，取这几部分的叠加作为散列地址
      - 关键字位数很多，每一位上数字分布大致均匀时，可以采用折叠法得到散列地址

    - .....

  - 不同的情况，不同的散列函数会发挥不同的性能，无法笼统的说那种散列函数最好。散列函数的目标都是为了将产生冲突的可能性尽可能地降低

- 处理冲突

  - 【任何设计出来的散列函数都不可能绝对地避免冲突】，必须考虑在发生冲突时如何进行处理
  - 处理方法

    - 开放定址法

      - 概念：可以存放新表项的空闲地址，既向它的同义词表项开放，也向它的非同义词表项开放
      - 增量取值方法

        - 线性探测法
        - 平方探测法
        - 再散列法（双散列法）
        - 伪随机序列法

      - 注意事项

        - 不能随便【物理删除】表中已有元素，删除将会截断具有相同散列地址元素的查找地址，牵涉元素广
        - 删除元素需要【单独做标记】，采用【逻辑删除】
        - 逻辑删除会导致散列表表面上看上满的，实际上很多位置都是没有被利用的，【需要定期维护，将删除标记的元素物理删除】

    - 拉链（链接）法

      - 概念：为避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中【由散列地址唯一标识】
      - 【重要】适用于经常进行插入和删除的情况

    - 拉链法处理冲突时不存在聚集现象，用线性探测法处理冲突时容易产生聚集现象

- 性能分析

  - 装填因子：一个表的装满程度 =（表中的记录数）/ （散列表的长度）
  - 查找效率取决于

    - 散列函数
    - 处理冲突的方法
    - 【重要】装填因子

  - 散列表的平均查找长度依赖于【散列表的填装因子】
  - 填装因子越大，表示装填的越“满”，发生冲突的可能性就越大
  - 散列冲突导致散列表在查找过程中也是需要进行比较的。【查找效率仍然用平均查找长度来度量】
  - 冲突的产生概率与装填因子（表中记录数和表长）的大小成正比

### 模式匹配（字符串）

- 简单模式匹配

  - 概念：第一个字符串（模式串）在第二串（主串）中的位置
  - 基本过程：从主串指定字符开始（一般第一个）和模式串的第一个字符逐个比较....
  - 时间复杂度：O(n\*m)，n、m分别为主串和模式串的长度

- 【难点，直接看代码理解】KMP算法

  - 【重要】是对简单模式匹配的改造，时间复杂度在O(n+m)的数量集上
  - 【建议手动模拟】基本过程

    - 整个匹配过程，没有进行指针回溯
    - 每趟比较过程让子串向后滑动到一个合适位置， 让这个位置上的字符和主串中的那个字符比较
    - 【重要】next数组的求解实际是对某个位置找到最长的公共前缀

- 总结比较

  - 简单模式匹配时间复杂度：O(n\*m)
  - KMP算法的时间复杂度为O(n+m)
  - 一般情况下，简单模式匹配的实际执行时间可以近似到O(n+m)
  - 【重要】KMP算法的重要特点是主串指针不回溯

## 排序

### 基本概念和定义

- 排序：重新排列表中的元素，让表中的元素能够满足按照关键字递增或者递减的过程
- 算法的稳定性【非常重要】
- 排序算法是否具有稳定性并不能衡量一个算法的优劣【重要】
- 内部排序：在排序期间元素全部存放在内存中的排序

  - 关键字比较
  - 移动元素
  - 不是所有的内部排序算法都是基于比较操作的，例如：基数排序属于内部排序算法，但不是基于比较实现的

- 外部排序：在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

### 插入排序

- 基本思想：每次将一个待排序的记录，按关键字大小插入到前面已经排序好的子序列中，直到全部记录插入完成
- 直接插入排序

  - 最简单、最直观的插入排序算法
  - 性能分析

    - 空间效率：仅仅使用到了常数个辅助单元，空间复杂度为O(1)
    - 时间效率：排序过程中，需要向左侧有序子表中逐个插入元素，操作n-1次,每次操作都分为关键字比较和元素移动这两部分的次数非常依赖于待排序表的初始状态【重要】

      - 最好的情况：元素已经有序，每个元素之需要比较一次，不用移动元素，O(n)
      - 最坏的情况：元素逆序，比较多次，移动多次，O(n^2)
      - 平均情况：总的比较次数和总的移动次数均约等于为(n^2)/4

    - 稳定性: 【稳定】的排序算法
    - 适用性

      - 顺序存储的线性表
      - 链式存储的线性表
      - 大部分排序算法都仅仅适用于顺序存储的线性表【重要】

- 折半插入排序

  - 简述

    - 直接插入：边比较边移动

      - 确定插入位置
      - 腾出空间，元素复制到插入位置

    - 折半插入：先比较再统一移动

      - 确定好待插入的位置后，再统一地向后移动元素

  - 性能分析

    - 折半插入排序的比较次数与待排序表的初始状态无关，仅仅取决于表中的元素个数n
    - 移动元素的次数相比直接插入排序没有任何的改变
    - 直接插入排序和折半插入排序的比较次数一样，依赖于排序表的初始状态
    - 时间复杂度：O(n^2)
    - 稳定性：【稳定】的排序算法

- 希尔排序（缩小增量排序）

  - 基本思想：将待排序表分割成为若干个L[i,i+d,i+2d,....,i+kd]的子表，分别进行直接插入排序,当整个表元素“基本有序”的时候，再对全体记录进行一次直接插入排序
  - 基本实现步骤

    - 第一步：取一个小于n的步长d1 ，把待排序的表分成d1个组，所有距离为d1的倍数的记录放在同一个组中，对各组进行直接插入排序
    - 第二步：取第二个步长d2 < d1，重复第一步

  - 主要操作

    - 确认步长，分组
    - 对分组元素进行直接插入排序

  - 性能分析

    - 空间效率：仅仅使用到了常数个辅助单元，O(1)
    - 时间效率

      - 直接插入排序

        - 是顺序的，时间复杂度最最小，O(n)
        - 是逆序的，时间复杂度最大，O(n^2)
        - 是局部有序的，即部分顺序、部分逆序，此时的时间复杂度介于两者之间，O(n)~O(n^2)

      - 取决于增量序列函数

        - 优于折半插入排序
        - 最坏情况为O(n^2)

    - 稳定性：【不稳定】，存在相同值元素分在不同的组进行直接插入排序
    - 适用性：仅仅适用于顺序存储的线性表，虽然采用过程中有采用直接插入排序，但增量序列不为1的时候，需要随机存取，链式存储的时候无法满足

### 交换排序

- 冒泡排序

  - 算法简单、思路直接、十分常用但考查少
  - 两元素交换方案

    - 临时变量法
    - 加减法

  - 空间效率

    - 仅使用了常数个辅助单元
    - 空间复杂度为O(1)

  - 时间效率

    - 最好情况（顺序）

      - 比较次数：n-1
      - 移动次数：0
      - 时间复杂度为：O(n)

    - 最坏情况（逆序）

      - 比较次数：每趟比较(n-i)次
      - 移动次数：每趟移动3次
      - 时间复杂度为：O(n^2)

    - 时间复杂度为：O(n^2)

  - 稳定性：【稳定】

- 快速排序

  - 基于递归、理解困难、分而治之、关键基准pivot划分
  - 空间效率

    - 基于递归实现，需要借助递归工作栈来保存每一次递归调用的必要信息
    - 最坏情况：进行n-1次递归，O(n)
    - 最好情况: log2(n+1) 向上取整
    - 平均情况： O((n+1)以2为底的对数)

  - 时间效率

    - 运行时间与划分操作Partition()函数【不对称相关】
    - 最坏情况

      - 数组长度为n
      - 左侧快排的数组长度为n-1,有n-1个元素【初始排序表基本有序】
      - 右侧快排的数组长度为0，有0个元素【初始排序表基本逆序】
      - 时间复杂度为：O(n^2）

    - 效率优化

      - 递归过程中划分得到的子序列规模较小时候，不再递归调用快速排序 ----->改用直接插入排序【时间复杂度最好O(n),性能好】
      - 尽量选择能将数据中分的基准值元素
      - 随机从当前表中选取基准值元素，几乎避免最坏情况的发生

  - 稳定性：【不稳定】，存在值相同的元素，位置与最终位置不一致情况
  - 重要：【是所有内部算法中平均新能最优的排序算法】

### 选择排序（TBD）

- 简单选择排序
- 堆排序

### 归并排序（TBD）

### 基数排序

- 很特别的排序算法，【不是基于比较进行排序的】
- 基本步骤【趟数取决于元素的最大位数】

  - 分配：依次考察线性表元素，放入队列中
  - 收集：各队列中结点一次首尾相接，组成新的线性表

- 分类

  - 最高位优先排序【MSD】
  - 最低位优先排序【LSD】

- 性能分析

  - 空间效率：

    - 一趟排序需要r个队列的辅助存储空间，后续排序这些队列将会复用
    - 空间复杂度为：O(n)

  - 时间效率

    - 进行d趟分配和收集操作

      - 一趟分配需要O(n)
      - 一趟收集需要O(r)

    - 平均情况：时间复杂度为O(d\*(n+r))
    - 【重要】算法的时间效率与初始排序表状态无关，依赖于分配和收集操作

  - 稳定性：【稳定】<----- 按位排序必须稳定

### 内部排序

- 各算法性能比较

  - 从时间复杂度来看

    - 平均情况O(n^2)

      - 直接插入排序
      - 简单选择排序
      - 冒泡排序

    - 最好情况O(n)【顺序情况】

      - 直接插入排序
      - 冒泡排序

    - O(nlog2n)

      - 归并排序与初始序列的排序列无关，所有情况下时间复杂度都是O(nlog2n)
      - 堆排序利用数据结构堆，线性时间完成建堆，在O(nlog2n)内完成排序
      - 快排平均性能可以达到O(nlog2n)【性能常常优于其他排序算法】

    - 基于分治法的思想

      - 快速排序
      - 归并排序

    - 简单选择排序与序列的初始值状态无关
    - 希尔排序是插入排序的拓展，在大规模排序中可以达到很高的效率n^1.3~2

  - 从空间复杂度来看

    - 借助常数个辅助空间

      - 简单选择排序
      - 插入排序
      - 冒泡排序
      - 希尔排序
      - 堆排序

    - 快速排序在空间上只适用一个小的辅助栈，实现【递归】

      - 平均情况：O(log2n)
      - 最坏情况：O(n)

    - 二路归并排序需要较多的辅助空间，为O(n)，可以采取时间换空间的思路来减少辅助空间【不建议，导致算法复杂】

  - 从稳定性来看

    - 稳定的

      - 插入排序
      - 冒泡排序
      - 归并排序
      - 基数排序

    - 不稳定

      - 简单选择排序
      - 快速排序
      - 希尔排序
      - 堆排序

  - 从过程特征来看

    - 冒泡排序和堆排序每次循环都能拿到当前的最大值或最小值
    - 快速排序每次循环都能确定一个元素到最终位置上
    - 冒泡排序每一趟冒泡也能确定一个元素到最终位置上

- 算法运用

  - 排序方法选取需要考虑的因素

    - 待排序的元素数目n
    - 元素本身信息量大小
    - 关键字的结构和分布情况
    - 稳定性的要求
    - 语言工具、存储结构、辅助空间大小

  - 排序算法小结

    - n很小时选择

      - 直接插入排序
      - 简单插入排序

    - 关键字基本【有序】时选择

      - 直接插入排序
      - 冒泡排序

    - n较大时选择O(nlog2n)的排序

      - 快速排序【不稳定】
      - 堆排序【不稳定】
      - 归并排序【稳定】

    - n很大且关键字位较少、可分解，建议选择【基数排序】
    - 信息量较大、元素较多，存储结构可以采用【链表】，减少不必要的时间去元素移动

  - 快速排序被认为是基于比较的内部排序中最好的排序方法
  - 基于比较的排序算法中，每次比较两个关键字之后，只有两种情况（大于|小于）----> 二叉树， 时间复杂度至少为O(nlog2n)

### 外部排序

- 基本概念

  - 内部排序：排序方法在内存中进行的排序
  - 外部排序：排序过程中需要多次进行内存、外存交换，对外存文件中的记录进行排序后【仍然存放在外存原有文件中】的排序
  - 外部排序原因：对大文件进行排序，内存控件有限，文件中信息量庞大，无法将整个文件拷贝进内存中进行排序，需要多次调入内存进行排序

- 外部排序方法

  - 分类【依据外存设备的不同】

    - 磁盘文件排序
    - 磁带文件排序

  - 分布方式

    - 磁盘是直接存取设备
    - 磁带是顺序存取设备

  - 文件通常是【按块存储】在磁盘上，操作系统也是【按块读取】磁盘上的信息
  - 外部排序中时间代价主要考虑【访问磁盘的次数】，即I/O次数
  - 【通常采用归并排序方法】

### 补充总结和复习

- 元素个数不是很大（n<1000）

  - 直接插入排序【稳定】
  - 冒泡排序【稳定】
  - 简单选择排序【不稳定】
  - 空间复杂度都为O(1)，只需要一个辅助元素
  - 平均时间复杂度都为O(n^2)

- 中等规模的元素，希尔排序【不稳定】是非常好的选择，比直接插入排序要好（n越大越明显），不占用额外内存空间，减少直接排序次数
- 元素个数很多（n很大）

  - 快速排序【不稳定】

    - 最通用、高效的内部排序算法
    - 平均时间复杂度为O(nlog2n)
    - 一般空间复杂度为O(log2n)
    - 最快情况，性能退化【元素基本有序时】

      - 时间复杂度提高到O(n^2)
      - 空间复杂度提高到O(n)
      - 解决方案： 三者(low,mid,high)取中，获取枢纽值【注意严版采用的是low,high】

  - 堆排序【不稳定】

    - 高效的内部排序算法
    - 时间复杂度为O(nlog2n)
    - 没啥最坏情况，基本不需要额外的存储空间

  - 归并排序【稳定】

    - 性能与初始化元素序列无关
    - 时间复杂度总为O(nlog2n)
    - 【明显缺点】：需要O(n)的额外存储空间

  - 基数排序【稳定】

    - 特殊的排序算法
    - 除了对元素序列的关键字比较，更对关键字的不同位也进行处理和比较
    - 具有线性增长的时间复杂度O(d\*(n+r))，适用性比较低、应用场景相对少
    - 需要额外的存储空间，一般用队列来实现桶

- 【重要】不同的排序算法缓和使用，往往能够对算法进行不错的改进，获得更好的性能