[toc]

软件设计师笔记03_数据结构_精简考点

科目一考试中占5分左右。

线性表

线性表常采用顺序存储和链式存储，主要的基本操作是插入、删除和查找等。

• 给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动 (n-1)/2 个元素。
• 当线性表进行顺序存储时，逻辑上相邻的元素，其物理位置也相邻。此时查询元素的时间复杂度为O(1)，也就是常量级。此时插入元素就需要移动一些元素了，因此插入元素的时间复杂度为O(n)，其中n为线性表的长度。
• 当线性表进行链式存储时，逻辑上相邻的元素，其物理位置不要求相邻。此时查找元素和插入元素的时间复杂度都为O(n)。

单向循环链表由于指针方向是单向的。因此访问其直接后继的运算时间复杂度为O(1)，访问其直接前驱的运算时间复杂度为O(n)。

栈

• 栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此 实现函数或过程的递归调用及返回处理时 必须用栈。
• 表达式采用逆波兰式(后缀式)表示时，利用（ 栈 ）进行求值。

存放操作数的栈的容量

如何计算存放操作数的栈的至少容量：

1. 先将表达式转换为后缀式。
2. 然后看后缀式中的第一个运算符号前的操作数个数。那就是存放操作数的栈的至少容量。

例题

当利用栈对算术表达式10*(40-30/5)+20求值时，存放操作数的栈(初始为空)的容星至少为__,才能满足暂存该表达式中的运算数或运算结果的要求。

解法

1. 先将表达式转换为后缀式 10 40 30 5 / - * 20 +
2. 然后看后缀式中的第一个运算符号前的操作数个数。那就是存放操作数的栈的容量。
3. 后缀式 10 40 30 5 / - * 20 + 中第一个运算符号前的操作数个数是4个。

则存放该操作树的栈的容量为4

队列

• 循环队列中求队头元素的指针的计算公式为：(rear-len+1+M) % M 其中rear是队尾指针，len是队列长度，M是队列存储容量。
• 必须采用队列结构的是 打印序列。

真题案例1

输出受限的双端队列是指元素可以从队列的两端输入，但只能从队列的一端输出，如下图所示，若有e1,e2,e3,e4依次进入输出受限的双端队列，则得不到输出序列 （ ）。

• A e4,e3,e2,e1
• B e4,e2,e1,e3
• C e4,e3,e1,e2
• D e4,e2,e3,e1

正确答案是D

• 选项 A：e4,e3,e2,e1 输入过程：让e1、e2、e3、e4依次从左端输入队列。输出过程：由于只能从一端输出，此时队列中元素顺序从左到右为e4 e3 e2 e1。按照先进后出原则，依次输出e4、e3、e2、e1，该输出序列可以得到。

• 选项 B：e4,e2,e1,e3输入过程：先让e1、e2从左端输入，e3 从右端输入 e4再从左端输入。此时队列中元素顺序从左到右为e4 e2 e1 e3。按照先进后出原则，依次输出e4,e2,e1,e3。该输出序列可以得到。

• 选项 C：e4,e3,e1,e2输入过程：让e1、e2从左端输入，e3、e4从右端输入。此时队列中元素顺序从左到右为e4,e3,e1,e2。按照先进后出原则，依次输出e4,e3,e1,e2。该输出序列可以得到。

• 选项 D：e4,e2,e3,e1输入过程：尝试各种从两端输入元素的方式。若要先输出e4，e4需最后进入队列且在队尾（输出端 ）。矛盾分析：若e4在队尾，当输出e4后，接下来要输出e2，由于只能从一端输出，在e4输出后，要输出e2，则e2需在队尾，但此时若e2在队尾，e3就无法在e2之前输出，所以无法得到该输出序列。

二维数组

二维数组的特点如下：

1. 数据元素数目固定。
2. 数据元素具有相同的类型。
3. 数据元素的下标关系具有上下界约束且下标有序。

一个m行n列的数组表示如下

数组存储地址的计算公式

假设每个数组元素占用内存长度为len，起始地址为a，存储地址计算如下：

一维数组的存储地址计算公式 如何理解？

一维数组 a[n]， a[i] 的地址公式是：( a + i \times len)

二维数组(按行优先存储)的存储地址计算公式 如何理解？

1. 二维数组按行存，就是先存完第 0 行所有元素，再存第 1 行，以此类推。
2. 要到 a[i][j]，你得先跳过前 i 行，再在第i行里跳过 j 个元素。
   • 前 i 行：每行有 n 个元素。那么一共是 i×n 个元素
   • 第 i 行里：再跳过 j 个元素。总共跳过 i×n + j 个元素
3. 另外每个元素占len字节，所以偏移量是 (i×n + j) × len。

所以当二维数组行有n个，列有m个时，按行优先存储的a[i][j] 的地址公式是：a + (i * n + j) * len

二维数组(按列优先存储)的存储地址计算公式 如何理解？

1. 二维数组按列存，就是先存完第 0 列所有元素，再存第 1 列，以此类推。
2. 要到 a[i][j]，你得先跳过前 j 列，再在第j列里跳过 i 个元素。
   • 前 j 列：每列有 m 个元素。那么一共是 j×m 个元素
   • 第 j 列里：再跳过 i 个元素。总共跳过 j×m + i 个元素
3. 另外每个元素占len字节，所以偏移量是 (j×m + i) × len。

所以当二维数组行有n个，列有m个时，按列优先存储的a[i][j] 的地址公式是：a + (j * m + i) * len

快速记忆表

存储方式	公式核心	关键区别
一维数组	i 直接乘len	只有一个下标
二维a[n][m]按行	i×n + j	先乘 “列数 n”，再加列下标 j
二维a[n][m]按列	j×m + i	先乘 “行数 m”，再加行下标 i

例题

案例1

在一个二维数组A中，假设每个数组元素的长度为3个存储单元，行下标i为0-8，列下标j为0-9，从首地址SA开始连续存放，在这种情况下，元素A[8][5]的起始地址为（ ）。

• A SA+141
• B SA+144
• C SA+222
• D SA+255

正确答案：D

二维数组按行优先存储，即先存储完一行的所有元素，再存储下一行。

那么元素A[8][5]是二维数组中的第86个元素。

元素A[8][5]的起始地址 SA + 85 * 3 = SA + 255

例题2

[2024年上半年] 已知二维数组A按行优先方式存储，每个元素占用2个存储单元，第一个元素A[0][0]的地址为100，元素A[3][3]的存储地址是220，则元素A[5][5]的地址是（ ）。

• A 300
• B 310
• C 306
• D 296

正确答案：A

解析：当二维数组按行存储的时候。由元素A[3][3]的存储地址220，可以得到该二维数组的列数为19

然后根据公式 A[5][5] = 100+(5*19+5)*2 = 300

矩阵

三对角矩阵公式如图所示

真题范例1

设有n阶三对角矩阵A，即非零元素都位于主对角线以及与主对角线平行且紧邻的两条对角线上，现对该矩阵进行按行压缩存储，若其压储空间用数组B表示，A的元素下标从0开始，B的元素下标从1开始。已知A[0,0]存储在B[1]，A[n-1,n-1]存储在B[3n-2]，那么非零元素A[i，j](0≤i<n，0≤j<n，|i-j|≤1)存储在B[（ ）]。

A 2i+j-1 B 2i+j C 2i+j+1 D 3i-j+1

正确答案：C

n阶三对角矩阵如下图所示。

在元素ai,y之前共有i行（行号从0到i-1 )，除了第一行外，其余每行都是3个元素, 因此这i行上的元素个数为(3*i-1);在行号为i时，排列在ai,y之前的元素个数为j-i+1, 合计2i+j个元素，因此元素ai,y存储在B[]中的下标为2i+j+1(因数组B是从下标1开始存放元素的）。

真题范例2

某n阶的三对角矩阵A 如下图所示，按行将元素存储在一维数组M中，设a1,1存储在M[1]，那么ai,j (1<=i，j<=n且ai,j位于三条对角线中)存储在M（ ）。

A i+2j B 2i+j C i+2j-2 D 2i+j-2

按行存储时，aij之前有i-1行，除了第一行外，每行有3个元素，在第i行上，其之前有j-i+1个元素，因此aij之前共有(i-1)*3-1+j-i+1=2i+j-3个元素，由于ai,1存储在M[1]，所以 ai,j存储在M[2i+j-3+1]。

树

树的基本概念 ⭐️

1. 树的深度。一棵树的最大层数为该树的深度（或高度）。
2. 结点的度。一个结点拥有子树的个数称为该结点的度。
3. 叶子结点。叶子结点是指度为 0 的结点。
4. 结点的层次。该结点所在树中的层次，即为该结点的层次。
5. 有序/无序树。如果树中各结点的各个子树是从左到右有序排列且不能交换时，则称该树为有序树。否则称为无序树。

二叉树 ⭐️

二叉树与普通树的区别在于，每个节点最多只有两个孩子结点。二叉树中结点的子树分为左子树和右子树。

二叉树的性质

• 一个深度为k的二叉树最多有 2^k^-1 个结点（k>=1）。
• 在二叉树的第i层上最多有个 2^(i-1)^ 个结点(i>=1)。
• 对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。即度为0的结点数比度为2的结点数多1个。

特殊的二叉树 ⭐️

满二叉树

如果一个二叉树的层数为 K，结点总数为 2^k^ - 1 个，则它就是满二叉树，如图a所示。

完全二叉树

在一个深度为 h 的完全二叉树中，除第 h 层外（最后一层），其他各层都是满的。第 h 层所有的结点都必须从左到右依次放置，不能留空，如图 b 所示。 则这样的二叉树为完全二叉树。

平衡二叉树

平衡二叉树：树中任一结点的左右子树高度之差不超过1。

查找二叉树

查找二叉树：又称之为排序二叉树。任一结点的权值，大于其左孩子结点，小于其右孩子结点。中序遍历结果有序。

二叉树的存储结构 ⭐️

顺序存储

二叉树的顺序存储结构：顺序存储，就是用一组连续的存储单元存储二叉树中的节点，按照从上到下，从左到右的顺序依次存储每个节点。

在采用顺序存储时，完全二叉树与一般的二叉树相比节省了空间，这是因为一般二叉树需要添加一些“虚结点”而造成了空间的浪费，如图所示。

链式存储

二叉树的链式存储结构：一般用二叉链表来存储二叉树节点，二叉链表中除了该节点本身的数据外，还存储有左孩子结点的指针、右孩子结点的指针。每个二叉链表节点存储一个二叉树节点，头指针则指向根节点

在采用链式存储时，二叉树的链式存储可以分为二叉链表和三叉链表的存储结构，如图所示

对于完全二叉树，若某个节点在数组中的存储位置为i，则其左孩子的存储位置为2i，右孩子的存储位置为2i+1。

二叉树的遍历 ⭐️

二叉树是一个非线性结构，而对二叉树的遍历本质上是对一个非线性结构进行线性访问的过程。通过这种遍历，可以将二叉树这种非线性结构的数据转换为线性结构的数据，从而方便存储或处理等操作。

二叉树的遍历可以分为前序、中序、后序和层次遍历四种形式。这四种遍历方式产生的结果如图所示。

记忆点

• 先序（前序）遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根
• 层次遍历：按层次，从上到下，从左到右

先序遍历（口诀：先访问当前根节点，再递归遍历左子树，最后递归遍历右子树）（根左右）

技巧：只要看到节点，就先 “逛自己”，再 “逛左边”，最后 “逛右边”。

以上图为示例，详细说明如何进行先序遍历。

1. 第一步：处理根节点1。按先序遍历的顺序，我们要先处理1自己，再处理1的左子树（根是2），最后处理右子树（根是3）。
2. 第二步：遍历左子树（根为2）
   1. 先访问根节点2，输出2。
   2. 再访问根节点2的左子树（根4）。4没有左、右孩子，所以直接访问它。即输出4。
   3. 最后访问根节点2的右子树（根5）。继续按根左右的规则。
      1. 先访问根节点5，输出5。
      2. 处理5的左子树（根7）。继续按根左右的规则。因此先输出7，再输出8。
      3. 处理5的右子树（没有）。
   4. 因此2这棵子树的先序遍历结果为：2, 4, 5, 7, 8
3. 第三步：遍历右子树（根为3）
   1. 先访问根节点3，输出3。
   2. 访问根节点3的左子树（没有）。
   3. 访问根节点3的右子树（根6）。即输出6
   4. 因此3这棵子树的先序遍历结果为：3, 6
4. 第四步：把所有输出拼起来：1、2、4、5、7、8、3、6

中序遍历（口诀：先递归遍历左子树，再访问当前根，再递归遍历右子树）（左根右）

技巧：只要看到节点，就先 “逛左边”，再 “逛自己”，最后 “逛右边”。

以上图为示例，详细说明如何进行中序遍历。

1. 第一步：处理根节点1。按中序遍历的顺序，我们要先处理1的左子树（根是2），再处理1自己，最后处理右子树（根是3）。
2. 第二步：处理左子树2。对2这棵树，同样按左→根→右来：
   1. 先处理2的左子树（根4）。4没有左、右孩子，所以直接访问它。即输出4。
   2. 再访问根节点2。即输出 2
   3. 最后处理2的右子树（根5）。继续按左→根→右的规则。
      1. 处理5的左子树（根7）。继续按左→根→右的规则。因此先输出7，再输出8。
      2. 处理5的右子树（没有）。因此直接访问根节点5。即输出 5
   4. 因此2这棵子树的中序遍历结果为：4、2、7、8、5
3. 第三步：回到根节点1。此时输出1。
4. 第四步：处理右子树3。对3这棵树，同样按左→根→右来：
   1. 先处理3的左子树（没有）。
   2. 后访问根节点3。即输出 3
   3. 最后处理3的右子树，即输出6
   4. 因此3这棵子树的中序遍历结果为：3、6
5. 第五步：把所有输出拼起来：4、2、7、8、5、1、3、6

后序遍历（口诀：先递归遍历左子树，再递归遍历右子树，最后访问当前根节点）（左右根）

技巧：只要看到节点，就先 “逛左边”，再 “逛右边”，最后 “逛自己”。

以上图为示例，详细说明如何进行后序遍历。

1. 第一步：处理根节点1。按照后序遍历的顺序，即先处理1的左子树2，再处理1的右子树3，最后处理1自己。
2. 第二步：处理左子树2。同样按照左右根的规则。
   1. 先处理2的左子树4。4无左右，则直接输出4。
   2. 处理2的右子树5。5有左子树7。继续按左右根的规则。
   3. 处理5的左子树7。7有右子树8。继续按照左右根的规则。
   4. 处理7的右子树8，因为8没有左右子树，所以直接输出8。
   5. 处理节点7本身，输出7。
   6. 处理节点5本身，输出5。
   7. 处理节点2本身，输出2。
3. 第三步：处理右子树3。同样按照左右根的规则。
   1. 遍历3的右子树6：6无左右。因此输出6。
   2. 处理节点3本身，输出3。
4. 第四步：最后处理根节点1，输出1.
5. 第五步：把所有输出拼起来：4、8、7、5、2、6、3、1

层次遍历（口诀：一层一层来，从上到下 每层从左到右访问）

步骤：

1. 从根节点开始，访问根节点
2. 从根节点的左子树开始，访问左子树的所有节点
3. 从根节点的右子树开始，访问右子树的所有节点
4. 重复以上步骤，直到访问完所有节点

以上图为示例，详细说明如何进行层序遍历。

1. 第 1 层：1 → 输出：1
2. 第 2 层：2、3 → 输出：1, 2, 3
3. 第 3 层：4、5、6 → 输出：1, 2, 3, 4, 5, 6
4. 第 4 层：7 → 输出：1, 2, 3, 4, 5, 6, 7
5. 第 5 层：8 → 输出：1, 2, 3, 4, 5, 6, 7, 8

二叉树的构造（通过遍历的序列） ⭐️

单独一个序列无法确定一个二叉树。唯有根据先序遍历和中序遍历或后序遍历和中序遍历才能唯一确定一个二叉树。

必须是中序遍历搭配其他序列才能唯一确定一个二叉树。

根据先序遍历和中序遍历构造二叉树 ⭐️

根据先序遍历和中序遍历构造二叉树的过程如下：

1. 先序遍历的第一个节点就是根节点
2. 在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树
3. 递归地对左子树和右子树进行构造

根据后序遍历和中序遍历构造二叉树 ⭐️

根据后序遍历和中序遍历构造二叉树的过程如下：

1. 后序遍历的最后一个节点就是根节点
2. 在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树
3. 递归地对左子树和右子树进行构造

根据层序遍历和中序遍历构造二叉树 ⭐️

根据层序遍历和中序遍历构造二叉树的过程如下：

1. 层序遍历的第一个节点就是根节点
2. 在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树
3. 递归地对左子树和右子树进行构造

最优二叉树（哈夫曼树） ⭐️

哈夫曼树又称为最优二叉树，是一种带权路径长度最短的二叉树。

所谓树的带权路径长度，就是树中所有的叶子结点的权值乘上其到根结点的路径长度（若根结点为 0 层，叶子结点到根结点的路径长度为叶子结点的层数）。

基本概念

• 权：节点代表的值
• 路径是从树中一个结点到另一个结点之间的通路，路径上数目称为路径长度。
• 结点的路径长度：路径上的分支数目
• 结点的带权路径长度：该结点到根结点之间的路径长度乘以该节点的权值
• 树的带权路径长度：根节点到达每一个叶子节点之间的带权路径长度之和

树的带权路径长度（WPL）：树中所有叶子节点的带权路径长度之和。

真题范例1

对下面的二叉树进行顺序存储(用数组MEM表示)，已知结点A、B、C在MEM中对应元素的下标分别为1、2、3，那么结点D、E、F对应的数组元素下标为（ ）。

A 4、5、6 B 4、7、10 C 6、7、8 D 6、7、14

正确答案D

二叉树顺序存储规则： 对于完全二叉树，若根节点下标为i（本题中根节点A下标为1 ） ，则其左孩子节点下标为2i，右孩子节点下标为(2i + 1) 。

• 节点D：节点C下标为3，D是C的左孩子，根据规则，D的下标为 2x3=6。
• 节点E：E是C的右孩子，其下标为 2x3+1=7。
• 节点F：F是D的右孩子，D下标为6，所以F的下标为 2x6+1=14。
• 综上，节点D、E、F对应的数组元素下标为6、7、14，答案选 D。

构造最优二叉树（哈夫曼算法） ⭐️

如何构造最优二叉树？构造最优二叉树的哈夫曼算法步骤如下。

1. 假设有一组给定的权值集合 F，集合 F 里面包含一些权值节点。（比如{w₁, w₂, ..., wₙ}）。我们需要用这些权值节点构建一个最优二叉树。
2. 第一步：
   • 从集合F 中选择两个权值最小的节点。将它们作为左、右子树构造一棵新的二叉树，新树的根节点的权值为这两个节点的权值之和。
   • 把集合F 中删除这两个节点。并将新树根节点的权值加入到集合 F 中。
3. 第二步：
   • 从集合 F 剩下的节点中再次选择两个权值最小的节点，将它们作为新树的左、右子树，新树的根节点的权值为这两个节点的权值之和。
   • 把集合F 中删除这两个节点。并将新树根节点的权值加入到集合 F 中。
4. 重复上面步骤，直到所有节点都被合并为一棵树。

注意：

• 在构造新树的过程中，对于选出的两个权值节点，哪个作为左子树、哪个作为右子树并没有明确规定。这就导致：对于相同的一组权值，可能会构造出不同形状的最优二叉树。不过，不管形状如何变化，这些树的带权路径长度（WPL值）都是相同的，这是由权值本身决定的。
• 建议，每次选择两个权值最小的节点时，先选择权值较小的节点作为左子树，权值较大的节点作为右子树。

图 ⭐️

图是比树结构更复杂的一种非线性结构。

图的种类 ⭐️

• 无向图：图的顶点之间连接线是没有箭头的，不分方向。如图所示。
• 有向图：图的顶点之间连接线是箭头，表示从一个节点到另一个节点。如图所示。
• 无向完全图：在无向图中，若每个顶点都与其他顶点之间都有一条边相连，则称该图为无向完全图。无向完全图的n个结点的连线数为(n-1)+(n-2)+...+1 = n(n-1) / 2;
• 有向完全图：在有向图中，若每个顶点都与其他顶点之间都有两条有向边互相相连，则称该图为有向完全图。即顶点两两之间都有互通的两个箭头，则 n个节点有向完全图的的连线数为n(n-1)

图的基础概念 ⭐️

• 度：顶点的度是关联与该顶点的边的数目。若在有向图中，一个顶点的度为该顶点的出度和入度之和。
• 出度是以该顶点为起点的有向边的数目。
• 入度是以该顶点为终点的有向边的数目。
• 路径：存在一条通路，可以从一个顶点到达另一个顶点，有向图的路径也是有方向的。

其他概念

• 连通图：针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。

• 连通分量：无向图G中的极大连通子图称为其连通分量。

• 强连通图：针对有向图。若有向图任意节个顶点间都互相存在路径即存在v到u，也存在u到v的路径，则称为强连通图。

• 强连通分量：有向图G中的极大连通子图称为强连通分量。

• 网：若图中的边带有权值，则称该图为网。

图的遍历特点 ⭐️

深度优先遍历 ⭐️

深度优先遍历：从任一顶点出发，遍历到底，直至返回。再选取任一其他节点出发，重复这个过程直至遍历完整个图。

如图所示

深度优先遍历的时间复杂度

• 当图使用邻接矩阵表示时，深度优先搜索遍历该图的时间复杂度为O(n^2^)
• 当图使用邻接链表来表示时，深度优先搜索遍历该图的时间复杂度为O(n+e)。其中n为节点数，e为边数。

广度优先遍历 ⭐️

广度优先遍历：先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。

广度优先遍历的时间复杂度

广度优先遍历和深度优先搜索遍历图的时间复杂度相同，其不同之处仅仅在于对顶点的访问次序不同。

字符串匹配（KMP算法） ⭐️

KMP算法核心：利用已匹配信息，避免重复比较。

哈希表 ⭐️

哈希函数构造方法

1. 直接定址法：H(key) = a×key + b
2. 除留余数法：H(key) = key % p（p取质数）
3. 数字分析法：取数字的某些位作为哈希地址
4. 折叠法：将数字分段后相加

哈希冲突解决方法

方法	原理	特点
开放地址法	冲突时探测其他位置	线性探测、二次探测、双重哈希
链地址法	冲突时链表存储	常用，Java HashMap采用
再哈希法	换哈希函数	减少聚集
建立公共溢出区	冲突元素放溢出区	适合冲突少的情况

查找 ⭐️

• 顺序查找的平均查找长度为 (n+1) / 2。
• 哈希查找。时间复杂度：平均O(1)，最坏O(n)
• 二分查找。时间复杂度：O(logn)

二分查找 ⭐️

适用条件：有序表、顺序存储 时间复杂度：O(logn)

步骤：

1. 初始化low=0，high=n-1
2. 当low≤high时：
   • mid = (low+high)/2
   • 若a[mid]=key，查找成功
   • 若a[mid]<key，low=mid+1
   • 若a[mid]>key，high=mid-1

排序 ⭐️

稳定的排序方法：冒泡排序，直接插入排序。

常见排序方法对比如图所示

排序算法详细对比 ⭐

算法	平均时间	最坏时间	最好时间	空间复杂度	稳定性	特点
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定	简单，适合基本有序
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(logn)	不稳定	平均最快，常用
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定	外排序首选
插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定	小规模数据优
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	简单，交换次数少
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定	空间效率高
希尔排序	O(n^1.3)	O(n²)	O(n)	O(1)	不稳定	分组插入优化

关键记忆点

• 稳定排序：冒泡、插入、归并（口诀"帽插龟"）
• O(nlogn)算法：快速、归并、堆排序（口诀"快归堆"）
• 原地排序：除归并外大部分都是
• 最坏情况O(n²)：冒泡、插入、选择、快速（有序时）
• 平均速度：快速排序 ＞ 堆排序 ＞ 归并排序