考研数据结构自命题速成笔记

本文有几道例题的录屏讲解，见链接： https://pan.baidu.com/s/1wl2-3MvBgdWl7ngszDehHg?pwd=6666

一、概念

抽象数据类型（ADT）定义一个完整的数据结构：数据对象、数据关系、基本操作集

逻辑结构：线性、非线性

存储结构：顺序存储、链式存储、索引存储、散列存储

循环队列是一种数据结构

存储数据时，除了存储数据元素的值，还要存储数据元素之间的关系

链式存储设计，结点内的存储单元地址一定连续

算法：问题求解步骤的描述，准确、清晰、有穷
算法原地工作：指算法所需的辅助空间是常量

$O(n^2) => T(n) ≤ cn^2$

执行时间与 $n^2$ 成正比✅
问题规模仍然是 n
时间复杂度总考虑最坏的情况，以确保不会比它更长
同一个算法，实现语言的级别越高，执行效率越低

二、时间复杂度

# 阶乘算法，操作步骤只有一个乘法，因此n次就是O(n)
int fact(int n) {
    if (n<=1) return 1;
    return n*fact(n-1);
}

# 两个升序列表 m, n, 合并为长度 m+n 的升/降序列表，最坏情况是两两错开
# 因此每次选开头两个比较，小的放前，大的随后
# 等较短的列表排完后，另一个列表剩下的依次后放即可
# 因此时间复杂度为 O(max(m, n))，取决于较长的那个

数组排序的最小时间复杂度为 $$O(nlog_2n)$$
在插入链表时进行排序（即先检索链表看看排在哪，然后再插入链表），时间复杂度为 $O(n^2)$
长度为 n 链表接在长度为 m 的单链表后面，时间复杂度为 $O(m)$

先遍历 m，找到尾节点，然后接到 n 的头结点…

斐波那契数列

递归

int fibonacci(int n) {   // 第n项
    if (n == 1 || n == 2)
        return 1;
    else 
        return fibonacci(n-1) + fibonacci(n-2);
}

对于每一项，必须计算前两项，即 2 次计算，n 项就是 $O(2^n)$

非递归

int fibonacci(int n) {
    if (n <= 2)
        return 1;
    else {
        int num1 = 1;
        int num2 = 1;
        int i;
        for (i=3; i<n; i++) {
            num2 = num1 + num2;  // 前两项之和
            num1 = num2 - num1;   // num2 被覆盖掉了，所以用加出的和 减 num1 得到原先的 num2 并作为新的 num1
        }
        return num1 + num2;
    }
}

从第三项开始，只需要按照规律将前两项相加即可，时间复杂度为 $O(n)$

三、线性表

线性表是具有 n 个相同类型数据元素的有限序列
顺序存储结构的优点：存储密度大
线性表的顺序存储结构是一种随机存取的存储结构（不是~~顺序存取~~）

随机存取：根据起始地址加上序号，可以访问任一元素
访问元素 $O(1)$ ，增、删元素 $O(n)$

顺序存储需要连续的存储空间，例如 n 个空间已满，申请增加分配 m 个空间，则系统会开辟一个新的 n+m 个连续的存储空间，否则申请失败
顺序存储结构既能随机存取又能顺序存取，而链式结构只能进行顺序存取
静态链表需要分配较大的连续空间，插入和删除不需要移动元素
循环双链表判空条件是头结点（头指针）的 prior 和 next 都指向自身

为了体现循环、双链表的特性，空着的时候也要自给自足捏

静态链表中的指针表示的是下一个元素在数组中的位置

静态链表就是把一个数组拿来当链表，数组中每个元素记录本身的值和下一个元素的下标，从而形成链表的效果。因此静态链表插入和删除不需要移动元素，但需分配较大空间。

例题

注意，这个题有两个考点。

存的是下三角，问你的是上三角。而题目给出的是对称矩阵，因此 a[i][j] = a[j][i]，所以他问 上三角中a[i][i] 对应的下标，其实问的是 下三角中a[j][i] 的下标，因为你压根没存上三角，而矩阵压缩的意义就在于用压缩后数组中的一个元素对应原来矩阵中的两个对称值。
如果默认数组下标从 0 开始，则 a[i][j] 在第 i+1 行，算出来结果为 ${\frac{(1+j)j}2} + i$ ，但本题下标从 1 开始，因此结果为B

因此，压缩矩阵时，如果求出来的结果不对，不妨考虑换个起始下标。
此题也有另解，因为是按行存储，因此最后加的数一定是第二个下标对应的字符，也就是 j

广义表

广义表的长度：广义表中数据元素的数量。一个原子算做是一个元素，一个子表也只算做一个元素。
广义表的深度：指的是广义表中括号的重数。

1	C = ((a, b)) //长度为 1, 深度为 2

头尾链表存储结构

把每一个元素（不管是普通元素还是子表）都看做一个表，也就是挂载 1 ? ?
元素形式为 0 元素，而且必须挂载在 1 ? ? 下

D=(B, C)

扩展线性表存储结构

字母指出来第一个必是 1 ^ ?，1 表示是一个表，? 视情况而定，后面有元素就挂载，没有就也填 ^

|400x200

最外层的表里有几个元素（即广义表的长度），就挂载几个 ? ? ?，注意最后一个为 ? ? ^
如果是普通元素，则挂载 0 元素 ->/^
如果是一个子表，则挂载 1 -> ->/^。其中，中间的 -> 以此类推，依次挂载 0 元素 ->/^
如果子表中还有子表，如法炮制

四、栈和队列

栈和队列都是限制存取点/运算受限的线性结构
队列可以在两端运算，栈只能在一端进行运算
对于 n 个不同元素进栈，出栈序列个数为

${\frac{1}{n+1}}C_{2n}^n$

共享栈节省存储空间，降低发生上溢的可能

栈是不可能下溢的

循环队列
入队时，rear = (rear + 1) mod maxsize
出队时，front = (front + 1) mod maxsize
对列长度 = (rear + maxsize - front) mod maxsize
队满条件：(rear + 1) mod maxsize == front
队空条件：front = rear
队列先进先出（队尾进，队头出），因此入队时，队尾指针+1；出队时，队头指针+1

适合链队（核心就是你必须得有办法直接或间接地获得队首、队尾两个指针）
1. 带队首和队尾指针的非循环单链表
2. 只带队尾指针的循环单链表
3. 只有队首或队尾指针的循环双链表
栈的应用包括：递归、进制转换、迷宫求解、括号匹配、函数的局部变量
队列的应用包括：缓冲区

栈的应用包括递归，但递归不一定要用栈来消除

执行广度优先搜索图时，需要使用队列作为辅助存储空间
三对角矩阵说的是主对角线和与之上下平行的两条线
适用于压缩存储稀疏矩阵的结构：三元组表（理想）、十字链表

例题

A. ABCD 全入栈 $\implies$ CD 小括号 先算，栈内 AB $R_1$ $\implies$ B $R_1$ 乘法 先算，栈内 A $R_2$ $\implies$ 结果 综上，最大需 4 个存储单元

答案 AB 入栈 $\implies$ AB 小括号 先算，栈内 $R_1$ $\implies$ C 入栈，栈内 $R_1$ C 乘法 先算，栈内 $R_2$ $\implies$ D 入栈 $\implies$ 结果 综上，最大需 2 个存储单元

答案 A

见录屏讲解——扫描表达式入栈

五、树

树

n 个结点的树，所有结点的度数之和为 n-1 或 总度数 + 1 = 结点数

除了根结点外，每个结点都是某个结点的子结点，也就是对应着 1 个度

树的路径长度是从树根到每个结点的路径长度总和
把树看做有向图，则入度=出度。除了根结点，所有结点都只有 1 个入度，则总入度 = n-1
度为 n 的树，其结点数等于 $\displaystyle\sum_{i=0}^nn_i$ ，即结点为 0-n 的所有点个数之和

二叉树

度为 2 的树不一定是二叉树

二叉树要分左右，度为 2 的树可以不分

任意二叉树度为 2 的结点数 = 叶子结点数 - 1

对于所有结点数n，总读书d，有 $n_0+n_1+n_2 = n = d + 1 = 2n_2 + n_1 + 1 \implies n_2 = n_0 - 1$

$2^1+2^2+...+2^n = 2^{n+1}-2 < 2^{n+1}$ 这意味着再有鬼屎题目给你一个结点数很大的二叉树，不用去慢慢试着加，直接找一个尽可能大的但不超过它的 2 的指数次方，则下一个指数次必然超过

完全二叉树

h 层的满完全二叉树，一共有 $2^h-1$ 个结点
完全二叉树，若 $i≤\lfloor {\frac{n}2} \rfloor$ ，则结点 i 为分支结点，否则为叶子结点
完全二叉树， $n_1$ 要么是 0，要么是 1
因此判断两个结点是否属于同一层，可用 $\lfloor log_2p \rfloor = \lfloor log_2q \rfloor$

树存储方式

双亲表示法

孩子表示法

孩子兄弟表示法

树转化为二叉树

左孩子，右兄弟，将普通的树转化为二叉树

二叉树转化为森林

根据左孩子，右兄弟的原则，BAD 为三兄弟，则将兄弟结点拆分为单独的树，然后他的子结点继续按照左孩子、右兄弟的原则转化为二叉树

森林转化为二叉树

按照上一个的顺序，逆向操作即可。

遍历

二叉树的遍历

先、中、后其实说的就是根结点的位置

先序遍历：根结点、左结点、右结点
中序遍历：左结点、根结点、右结点
后序遍历：左结点、右结点、根结点

树、森林的遍历

先根-先序
后根-中序

先根遍历：先访问根结点，然后从左到右依次访问每一颗子树。先根遍历访问顺序和这棵树对应的二叉树的先序遍历相同
后根遍历：先从左到右依次访问每一颗子树，然后访问根结点。后根遍历访问顺序和这棵树对应的二叉树的中序遍历相同

树	二叉树	森林
先根	先序	先序
后根	中序	中序

二叉排序树

插入结点

左边小、右边大，然后依次插入即可

删除结点

删除后如下

查找

见录屏讲解——ASL 查找

平衡二叉树

平衡二叉树是一种特殊的二叉排序树，因此插入时就按排序树插入，然后不平衡再来旋转调整

也叫平衡树：任意结点的左右子数高度差的绝对值不超过 1，且子树都是平衡树
平衡因子：左子树和右子树的高度差，换言之其值只可能为 0, 1 或 -1
最小平衡二叉树公式 $F (n) = F (n-1) + F (n-2) + 1$ $F (n) = F (n - 1) + F (n - 2) + 1$
- $F(n)$ ：深度/高度为 n 的最小的(即结点数最少的)平衡二叉树。其中 $F(1)=1, F(2)=2$
- 按照公式，深度为 1, 2, 3，… 的最小二叉树所需结点分别为 1, 2, 4, 7, 12, 20…

插入

单转，转根；双转，先转子再转根

LL 插入（右转）

LL：左孩子的左子树
对根结点右转

RR 插入（左转）

RR：右孩子的右子树
左转：对根结点左转

LR 插入（先左转再右转）

LR：左孩子的右子树
先对左孩子左转，再对根结点右转

RL 插入（先右转再左转）

RL：先对右孩子右转，再对根结点左转

哈夫曼树

带权路径长度 (WPL) 最小的二叉树称为哈夫曼树，也称最优二叉树

构造哈夫曼树

首先，将给出的序列递增排序！！
每次找权值最小的两个点拼成一个树，使用过的结点做个标记；

若给一个字符串，每个字母出现的次数就是其权值
若给字符出现的概率，就把概率当权值，例如 9%，就取 9

将合并后的根结点按照排序插入序列中，继续从序列中选择最小的两个合并，以此类推；
如果要构造 K 叉哈夫曼树，注意看结点是否足够，不够的话采取和最佳归并树一样的解决方法

哈夫曼编码

从哈夫曼树的根结点，往左是 1，往右是 0，得出的即为哈夫曼编码（此处原稿为~~往左是 1/0，往右是 0/1~~，不知何解）

前缀编码：形成的哈夫曼编码中，没有任何一个编码是其他编码的前缀，则这组编码称为前缀编码

每走一步就是一个二进制编码。因此算出每个字母所需的编码乘出现的次数，加起来就是解码的二进制位数 ~~WTF？？这在说什么？~~

编码的总长度=每个字符对应哈夫曼编码的位数乘出现的次数，再相加
带权路径长度 WPL = 结点的权 x 从跟到结点的路径长度，再相加

归并树

就是把结点拼在一起变成树，二路归并就是两两拼，三路就是三个一起拼（参考哈夫曼树）
归并树的 WPL（带权路径长度）x 2 = 归并过程中磁盘 I/O 次数
最佳归并树：就是 WPL 最小的哈夫曼树
对于 K 路归并，若初始归并段（结点数）数量无法构成严格的 K 叉归并树，则需要补充几个长度为 0 的虚段(但是别在图里把 0 写出来！！！)，再进行 K 叉哈夫曼树的构造 ^un3nnj

注意要计算的是读字节数、还是写字节数、还是总的。例如上图 2+3=5 指的是读 5 个字节，写 5 个字节，因此这一趟的 I/O 为5x2=10字节

例题

$n_2 + n_1 + n_0 = 2n$ ，其中 $n_2 = n_0 - 1$ ，则 $n_1 = 2 (n-n_0) + 1$ ，即 $n_1$ 必为奇数，故选 C

n 个结点共有 2n 个指针域。由于每个结点都有一个入度，除了根结点外，故总共有 n-1 个入度，即非空指针域为 n-1 个，则空指针域为 2n-(n-1) = n+1 个，选 B

六、图

概念

450x350

判断有向图是否有环：深度优先、拓扑排序

连通图

无向图，任意两个顶点是联通的，则为连通图；否则为非连通图。对于 n 个顶点的无向图，

若连通，最少 n-1 条边
若非连通，最多 $C_{n-1}^2$ 条边

强连通图

有向图，任何一对顶点都是强连通的（可去可回，不一定非得是两点直接连接），则为强连通图。对于 n 个顶点的有向图，

若强连通，最少 n 条边

子图/生成子图

生成子图：包含了原图的所有顶点所构成的子图

连通分量（无向图）

首先要是子图，然后是连通的，最后要求极大（有尽可能多的点和边）

强连通分量（有向图）

首先要是子图，然后是强连通的（有去有回），最后要求极大（有尽可能多的点和边）

生成树（连通图）

包括全部顶点
极小连通子图

生成森林（非连通图）

|600x350

也就是对非连通图，先找他的极大连通子图（连通分量），然后对每个连通分量找包括所有顶点的极小连通子图（生成树）

图的存储

邻接矩阵法

无权值时，有边为 1，没有边为 0
如果边有权，则填权值，没有就填无穷
邻接矩阵为 A，则 $A^n[i][j]$ 表示从 i 到 j 长度为 n 的边有几条
邻接矩阵找深度优先：与邻接表法类似，从第一行开始走，到 1 的时候说明有边，然后跳到对应的结点的行；
从新的行按照上面的方法继续走，每当走到一个没出现过的新结点记录，以此类推走到底；
如果发现某个结点后面的都出现过了，当做全部走完了，然后往上回退到最近的没有走完的一层继续走；
邻接矩阵找深度优先：从第一行开始，把所有 1 都走一遍，记录下来；
把这个记录当做一个新的表，从第一个点开始，按照之前的方法，走完了就找后面一个点走；
直到所有的点都被遍历到。

邻接表法

n 个结点竖着写 n 行两列，左边填结点，右边空着表示指针域；
每个结点连着谁就顺次往后面挂，写完了就在最后一个点的指针域填 ^ 表示结束；
无向图 1 to 2 和 2 to 1 都要写，每个点后面挂着的点无所谓前后顺序；
有向图按照箭头顺序写就行了。
邻接表找深度优先：

从头开始往后走，每走一个做个标记；
每出现一个前面没有的新结点，就进到新节点里走，以此类推；
如果发现某个结点后面的都被走过了，全部标记，然后往上回退到最近的没有走完的一层继续走；
以此类推直到所有的结点都被标记。

用邻接表表示图进行深度优先遍历（DFS）时，通常实现其算法采用的结构是栈。

广度（BFS）采用的是队列。

十字链表法（有向图）

箭头箭头，当然是有箭的才叫头，另一个叫尾。因此对于弧而言，出度是弧尾，入度才是弧头

邻接多重表（无向图）

对于无向图，有几条边，就有几个边表结点。每个边对应一个边表结点，而不是两个，所以显然边表结点不唯一（例如 1-2, 2-1 都是同一条边）
如果边表结点的 ilink 和 jlink 分别是 0-1，则顶点表中，从 0 出来的第一个箭头直接指 0，而从 1 出来的箭头如果没有 1 开头的边表结点，就只能指向 1 后面的 jlink
边表结点中的数据域填的是结点对应的数组下标

最小生成树

Prim 算法

最小连通：你首先得跟已知点集连通，然后再去找最小

从顶点出发，找权最小的边，然后对当前所有遍历过的结点，找与它们相连的所有边中，权最小的，循环往复

Kruskal 算法

对整个图，依次找权最小的边，然后将剩余结点相连

最短路径（Dijkstra）

从顶点出发，能到的点写权值，不能到的写 $\infty$
找出各路径中最短的，将对应点加入点集，然后下一行以这个最小值对应的路径作为开始
每次计算路径时，如果新的路径长度小于旧的，才进行更新。大于旧的或者为 $\infty$ 则继承原来的

关键路径

选择题无所谓，解答题按照表格形式写！！！ 尤其是第二个表格

|600x300

对于每个结点，有最早时间和最晚时间
事件最早 ve (i)：把走到这个点的所有路径的权值相加，取最大的值

来的时候取最大值
事件最晚 vl (i)：最早填完了以后，把最后一个点的最早时间抄下来作为它的最晚时间。然后倒过去，用弧头的最晚时间依次减弧的权值，得到弧尾的最晚时间。对于有多个值的结点，取最小的值

回的时候取最小值
活动的最早时间 e (i)：就是这条弧起点（弧尾）对应结点的最早时间
活动的最晚时间 l (i)：就是这条弧终点（弧头）对应结点的最晚时间 - 弧的权值
关键活动：l(i)-e(i)=0 的活动
关键路径：l(i)-e(i)=0 的活动对应的路径

即 (最早时间，最晚时间) 相等的结点连成的路径（可能有多条）为关键路径，其路径上的活动即为关键活动

关键路径的长度：关键活动对应数值加起来
要加快/缩短整个工程的工期，必须同时改变所有的关键路径对应的关键活动

七、查找

折半（二分）查找

判定树就是二分查找的过程，用二叉树表示
判定二叉树是二叉排序树
向二叉查找树中插入一个元素，其时间复杂度大概为 O(log2n)
二分查找一个元素，查找长度就是从根结点开始的比较次数，不要去数树的深度！

~~ASL 成功=层数乘该层节点数，然后相加，再除总节点数~~

ASL 失败=所有缺了左/右孩子 (也就是查找失败的地方) 的结点数，然后乘层数，再相加，最后除总的失败地方的个数。注意，失败地方的层数，是按照它的父节点的层数算的，不要算到下一层去了。

分块查找

散列表

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数
散列表（hash 表）：根据关键字而进行直接访问的数据结构
常用的散列函数
1. 直接定址法：题目直接给出散列函数 H(key)
2. 除留余数法：设表长为 m，H(key)=key%p，p 为不大于 m 但最接近 m 的质数
装填因子
$\alpha = {\frac{n}{m}}$ ，其中n为表中记录数，m为散列表长度
散列表的平均查找长度依赖于散列因子。 $\alpha$ 越大，表示装填记录越满，发生冲突可能性越大；反之亦然

处理冲突

新地址的计算公式（无论是插入时还是处理冲突时，每一次都是在调用公式！！！）
- 根据不同的冲突处理办法， $d_i$ 取不同的值
- %m是指表长，不是给的 hash 函数中的 mod 值！注意和 ASL失败 作区分
说白了，插入的时候是在整个表的范围里插，所以%表长。而计算 ASL失败 时，仅仅只考虑 hash 函数映射出的真实长度，即 hash 函数的 mod 值

$H_i = (H(key) + d_i) \% m$

采用什么方法处理冲突的，计算查找次数时（也就是计算 ASL失败 时）就按照这个方法来
ASL成功以插入时的比较次数计算（与空比较也算作 1 次），除的是一共多少个数（元素个数）
ASL失败 以从当前元素开始，在整个表的范围内向后寻找到空为止的次数（开始算 1 次，找到空也算 1 次），除的的散列函数中的%数
如果没有说明表长，则**%数**是多少，表长就是多少
如果算出来的散列地址为负数，就从第一个位置开始倒着数

线性探测法

根据散列函数存，如果冲突，依次向后（ $d_i = 1$ ）寻找空位插入

平方 (二次) 探测法

$d_i = 0^2, 1^2, -1^2, 2^2, -2^2, ......, k^2, -k^2$ （本身，右左右左…）
k <= m/2
表长 m 必须为可以表示成 4k+3 的素数

双 (再) 散列法

$d_i = hash_2(key)$ ，也就是给了一个新的 hash 函数用来计算 d 值

注意，对于一个确定的数 key，解决它的冲突时 $d_i = hash_2(key)$ 显然为定值，因此可看做倍乘的线性探测法（ $d_i = hash_2(key)$ = 1 ）。而不同的 key 则 $d_i$ 不同

线性探测再散列的查找成功的平均查找长度 (告诉你数据个数，要求平均查找次数不超过几次，然后又没给装填因子，问你表长)

$ASL_{success} = \frac{1 + \frac1{1-\alpha}}{2}$

伪随机序列法

$d_i$ 为伪随机数序列

拉链法

按照给出的表长，对每个地址往下挂元素就完事了，冲突几个就挂几个，没有元素的就打 ^
如果你的表横着画，那么同一行的元素对应的查找次数一样，从上到下为 1, 2, 3…
如果你的表竖着画，那么同一列的元素对应的查找次数一样，从左到右为 1, 2, 3…
拉链法计算查找失败时，查找次数为已经挂载的元素个数+1，即与空指针的比较也要算作 1 次（~~也有观点认为不算，but who care?~~）

B/B+ 树

m 阶 B 树

每个结点最多 m 个子树，即至多含有 m-1 个关键字
非叶子结点，至少有两个子树（也就是必须得开叉）
除根结点外，非叶子结点至少含有 $\lceil {\frac{m}2} \rceil$ 个子树，即至少含有 $\lceil {\frac{m}2} \rceil -1$ 个关键字

也就是说不管你几阶 B 树，根结点可以只有 1 个

就想 3 阶 B 树就行了，每个结点最多 2 个关键字，满 3 个就要“进位”
2 个关键字形成 3 个间隔，每个间隔就是一颗子树

插入

结点分裂方法

先将插入的关键字写入结点，然后计算 $\lceil {\frac{m}2} \rceil$ 位置（按照 1, 2, 3 的顺序）对应的关键字

其实也就是中间位置

该结点左边的关键字原地不动，右边的放到新结点（记住，分裂一定会造就新结点！）
$\lceil {\frac{m}2} \rceil$ 位置对应的关键字按顺序插入该结点的父结点
如果父节点个数也超标了，继续执行上面的步骤
注意，插入的时候务必保持排序树！

删除

被删除关键字不在终端结点（不是叶子结点）

左子树多，找前驱替代
右子树多，找后继替代
左右一样多，合并两个子树，然后再删除目标关键字

被删除关键字在终端结点（是叶子结点）

如果叶子结点里关键字够多，直接删
如果叶子结点里关键字不够，找兄弟借，然后父子换位（父亲替代被删除的，然后借的那个兄弟，即儿子，当父亲）
如果兄弟不够借，父子合并（父亲下来和兄弟合并）

串的匹配

朴素模式匹配算法

主串长度为 n，模式串（你要找的串）长度为 m，将主串中所有长度为 m 的子串和模式串进行对比，直到找到一个完全匹配的子串，或所有子串都不匹配为止
主串中最多有 n-m+1 个子串

KMP 算法

next 数组

见录屏讲解——KMP 求 next 数组

nextval 数组

见录屏讲解——KMP 求 nextval

八、排序

排序总结

排序方法	时间复杂度 (平均)	时间复杂度 (最坏)	时间复杂度 (最好)	空间复杂度	稳定性
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
快速排序	$O(nlog_2n)$	$O(n^2)$	$O(nlog_2n)$	$O(nlog_2n)$	不稳定
归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
桶排序	$O(n+k)$	$O(n^2)$	$O(n)$	$O(n+k)$	稳定
基数排序	$O(n*k)$	$O(n*k)$	$O(n*k)$	$O(n+k)$	稳定

不稳定：快些选一堆好友来聊天（快速、希尔、选择、堆）

因为情绪不稳定，所以才要“快些选一堆好友来聊天”

时间快：快些归队（快速、希尔、归并、堆）
排序时注意，打下划线的元素意思为表示其稳定性，因此注意其摆放位置

插入排序

依次遍历所有元素，将待排序的元素插入前面已经排好序的子序列中

希尔排序

d 不一定为每次减半，可能由题目直接给出
如果没有给出 d，则根据 表长/2 自己设定一个初始值
对于某个元素，位置+d 之后超出表格，则原地不动
希尔排序的子表可以有若干位，只要+d 后仍在表内的都算

冒泡排序

每一趟都逐个比较相邻两个大小
从左边往右比较，冒泡到右边（无论升序还是降序）
从右往左比较，冒泡到左边

快速排序

快排快排，当然双管齐下（前、后双指针）才叫快

两个指针，low 指头，high 指尾。
以第一个元素为基准元素（可以将它暂存到别处，视作删除；也可以保留，总之要将其特别标识出来），high-- 从右边找比基准小的，找到了就放到 low;
接着 low++ 从左边找比基准大的，找到了就放到 high;
当 low = high 时，将刚刚暂存的基准元素放到 low = high，中间没有改变的元素照抄下来。至此，一趟排序完毕，且基准元素的最终位置已找到，后续无需移动！

快速排序一趟的完成标志：对于选定的基准元素，左边比他小，右边比他大，则一趟排序完成

选择排序

堆排序

向堆中插入一个元素，其时间复杂度为 O(log2n)
向堆插入：插入元素先放到堆底（数组最后），然后按照大/小根堆调整
从堆删除：将要删除的元素和堆底元素交换，然后把要删的删除，接着按照大/小根堆调整
堆的形状是一颗完全二叉树。

大根堆：根≥左、右
小根堆：根≤左、右

堆排序：
- 将给出的一组数据按照满二叉树逐行放进去；
- 按要求调整为大/小根堆（调整完成后的堆才叫初始堆）；
构造大/小根堆时注意，永远把子结点中最大的/最小的放上去
计算比较次数时，选取子结点中最大/最小这一步本身也需要一次对比
调整为大/小根堆时，从 $\lfloor {\frac{m}2} \rfloor$ 位置的结点开始，向前（向堆顶方向）检查
- 将堆顶和堆底（即二叉树最后一个结点）元素互换（从这一步开始才算做一次排序）；
- 堆顶元素换下去后用虚线连接，表示此后不再对它进行处理；
- 堆底元素换上去后，重新按照大/小根堆调整；
注意，此时应排除虚线连接的结点，将剩余结点视作新堆
- 调整完成后，视为一趟排序完成
- 以此类推，直到排序完成。