这是一个经久不衰的题目，不管你是校招新人还是资深大牛，面试过程中都有可能被问到这个问题，这篇文章会梳理一下常见的数据结构和排序算法，以及相关操作的时间复杂度和空间复杂度。
这个问题要答出花样的话，只能展示一下你的博闻强记。正常来说讲一下数组、栈、队列、单链表、双链表、哈希表就差不多了，不过有些比较常用的数据结构，比如用在 redis 和 RocksDB里面的跳表，比如数据库里常用来组织数据的 B tree，聊到这些之后下一步也可以引申着聊一聊 redis 和 RocksDB 的源码实现，这部分会在以后的文章聊到。面试说到底是公司和候选人的互相匹配，在面试过程中候选人必须要尽量避免面试官过于发散地提问，这样才能够保证面试过程能够尽可能完整地展示候选人自己的知识积累。
收敛面试范围有两种方式，一是要在简历上提到的项目必须是自己真实做过的项目（当然有些同学会包装一些自己没有做过的项目，不做评价），必须保证自己对简历上的项目足够熟悉，高级别的同学同时还需要对简历上涉及的项目在业界的同类方案也要有相当深入的了解。第二就是在面试过程中要学会引导面试官向一些特定的点提问，这一点也很重要。大多数人都不是维基百科，面试官发散的提问也是为了找到候选人比较熟悉和擅长的方向来深入挖掘，如果候选人能够自己积极主导这一过程，整个面试过程就能更加顺利。
好了话不多说，下面就是一些常见的数据结构和排序算法的时间复杂度和空间复杂度。
基本数据结构
| 数据结构 |
时间复杂度 |
|
|
|
|
|
|
|
空间复杂度 |
|
平均 |
|
|
|
最优 |
|
|
|
最坏 |
|
访问 |
查找 |
插入 |
删除 |
访问 |
查找 |
插入 |
删除 |
|
| 数组 |
$\Theta$(1) |
$\Theta$(n) |
$\Theta$(n) |
$\Theta$(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| 栈 |
$\Theta$(n) |
$\Theta$(n) |
$\Theta$(1) |
$\Theta$(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| 队列 |
$\Theta$(n) |
$\Theta$(n) |
$\Theta$(1) |
$\Theta$(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| 单链表 |
$\Theta$(n) |
$\Theta$(n) |
$\Theta$(1) |
$\Theta$(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| 双链表 |
$\Theta$(n) |
$\Theta$(n) |
$\Theta$(1) |
$\Theta$(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| 跳表 |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n log(n)) |
| 哈希表 |
N/A |
$\Theta$(1) |
$\Theta$(1) |
$\Theta$(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| 二叉查找树 |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| 笛卡尔树 |
N/A |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| B树 |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| 红黑树 |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| 伸展树（Splay tree） |
N/A |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
N/A |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| 自平衡二叉搜索树（AVL tree） |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| K-D树 |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
$\Theta$(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| 学习笔记：
1. 笛卡尔树（Cartesian Tree）是一种特殊的二叉树，它具有以下两个性质：
- 二叉搜索树性质：对于笛卡尔树中的每个节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。因此，笛卡尔树也是一个有效的二叉搜索树。
- 笛卡尔性质：对于笛卡尔树中的每个节点，其根节点在中序遍历中的位置对应于原始数据数组中对应元素的位置。换句话说，笛卡尔树的根节点对应于原始数组中最大（或最小）的元素，根节点的左子树对应于原始数组中根节点左边的部分，右子树对应于原始数组中根节点右边的部分。
笛卡尔树通常用于解决与序列相关的问题，如最大矩形面积、下一个更大元素等。通过构建笛卡尔树，可以在O(n)的时间复杂度内解决这些问题。
构建笛卡尔树的常用方法是使用单调栈。具体步骤如下：
1. 从左到右遍历原始数据数组。
2. 对于每个元素，将其作为新节点插入笛卡尔树中。
- 如果当前节点的值大于栈顶节点的值，将当前节点作为栈顶节点的右子节点，并将栈顶节点弹出栈，直到栈为空或当前节点的值小于栈顶节点的值。
- 如果当前节点的值小于栈顶节点的值，将当前节点作为栈顶节点的左子节点。
3. 将所有剩余的节点依次作为栈顶节点的右子节点，并弹出栈中的节点。
最终得到的树即为笛卡尔树。
笛卡尔树的特性使得它在某些问题上具有高效的解决方案，但并不是所有问题都适合使用笛卡尔树。在实际应用中，需要根据具体问题的特点和要求来选择合适的数据结构和算法。
2. 伸展树（Splay Tree）是一种自平衡的二叉搜索树，它通过重新组织树的结构来优化频繁访问的节点，使得这些节点更接近根节点，从而提高查找、插入和删除操作的性能。
伸展树的主要特点是每次对节点的访问（查找、插入、删除）都会将被访问的节点旋转至根节点，这个过程称为"伸展"。通过伸展操作，伸展树会调整树的形状，使得最近被访问的节点移动到树的根部，以期望在之后的操作中更快地访问到这些节点。
伸展树的伸展操作通过一系列的旋转来改变树的结构。旋转操作包括"左旋"和"右旋"，通过交换节点的位置来调整树的平衡性。伸展树的伸展操作基于"近似二叉树"（Approximate Binary Tree）的思想，通过将节点向上移动，使得频繁访问的节点更靠近根节点，同时保持树的有序性。
伸展树的优点在于它适应了访问模式的变化，将频繁访问的节点放置在树的上层，从而减少了访问路径的长度，提高了操作的效率。另外，伸展树没有复杂的平衡因子或调整操作，相对于其他平衡二叉搜索树（如AVL树、红黑树），实现起来更加简单。
然而，伸展树的最坏情况时间复杂度为O(n)，其中n为树中的节点数，因为伸展操作可能导致树的高度线性增长。因此，在某些特定的访问模式下，伸展树的性能可能不如其他平衡二叉搜索树稳定。此外，伸展树的平均性能与操作的访问模式密切相关。
伸展树在实际应用中常用于缓存、动态搜索和频繁访问的数据结构等场景，但需要根据具体情况评估其适用性，并注意控制树的深度，避免退化为链表。
3. 自平衡二叉搜索树（Self-Balancing Binary Search Tree）是一种二叉搜索树，在插入和删除操作后可以自动调整树的结构，以保持树的平衡性，从而提供较为稳定的性能。
二叉搜索树是一种有序的二叉树，其中每个节点的左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。它的主要优点是在具有良好平衡性的情况下，查找、插入和删除等操作的平均时间复杂度为O(log n)，其中n为树中节点的数量。
然而，普通的二叉搜索树在频繁的插入和删除操作后，可能会出现不平衡的情况，导致树的高度增加，进而降低了性能。为了解决这个问题，自平衡二叉搜索树引入了各种自平衡的算法和数据结构，以在操作后保持树的平衡。
常见的自平衡二叉搜索树包括：
1. AVL树：通过旋转操作来保持树的平衡，确保左子树和右子树的高度差不超过1。
2. 红黑树：使用颜色标记和旋转操作来保持树的平衡，保证树的高度近似平衡，并满足一些附加条件。
3. B树和B+树：多路搜索树，通过调整节点的数量来保持树的平衡，适用于大规模数据存储和检索场景。
4. Splay树：通过伸展操作将访问的节点移动到根节点，实现最近访问的节点更容易访问到，提高访问性能。
这些自平衡二叉搜索树的具体实现方式和调整策略有所不同，但它们的共同目标是通过动态调整树的结构，使得树的高度保持较小，从而提供较高的性能和效率。
根据具体应用场景和需求，选择合适的自平衡二叉搜索树可以提供更稳定和高效的数据存储和检索能力。
4. KD树（K-Dimensional Tree）是一种用于对k维空间中的点集进行分割和组织的数据结构。它是二叉搜索树的一种扩展形式，用于支持高维数据的快速搜索和近邻查找。
在KD树中，每个节点代表k维空间中的一个点，并根据该点的坐标进行分割。具体来说，树的每一层根据一个维度（坐标轴）选择一个切分超平面，将空间划分为两个子空间。左子树表示切分超平面左侧的子空间，右子树表示切分超平面右侧的子空间。
构建KD树的过程如下：
1. 选择切分维度：从k个维度中选择一个维度作为当前层的切分维度。
2. 选择切分值：在选定的切分维度上选择一个值作为切分超平面。
3. 划分子空间：将当前层的点集根据切分超平面分割为左右两个子空间，并将点集中小于等于切分值的点放入左子树，大于切分值的点放入右子树。
4. 递归构建子树：对左右子空间递归执行以上步骤，构建子树。
构建完成后，KD树可以提供以下常见操作：
- 搜索：根据给定的查询点，在KD树中进行搜索，找到最近的点或满足某种条件的点。
- 插入：向KD树中插入一个新的点。
- 删除：从KD树中删除一个指定的点。
KD树在高维数据集中可以高效地进行搜索和近邻查找，因为它可以根据数据在不同维度上的切分进行快速剪枝和定位。然而，在数据维度非常高时，KD树的效率可能会下降，这时可以考虑其他数据结构或使用降维等方法来处理高维数据。
|
排序算法
聊完数据结构，基本上都会聊一聊排序算法了，说起来其实挺羞耻的，我只会写个快排，我自己的经验是面试基本不会考这个，考的话最多也只会写个快排。不过技多不压身，多看看总没有坏处。
| 排序算法 |
时间复杂度 |
|
|
空间复杂度 |
| 快速排序 |
$\Omega$(n log(n)) |
$\Theta$(n log(n)) |
O(n^2) |
O(log(n)) |
| 归并排序 |
$\Omega$(n log(n)) |
$\Theta$(n log(n)) |
O(n log(n)) |
O(n) |
| 归并插入排序 |
$\Omega$(n) |
$\Theta$(n log(n)) |
O(n log(n)) |
O(n) |
| 堆排序 |
$\Omega$(n log(n)) |
$\Theta$(n log(n)) |
O(n log(n)) |
O(1) |
| 冒泡排序 |
$\Omega$(n) |
$\Theta$(n^2) |
O(n^2) |
O(1) |
| 插入排序 |
$\Omega$(n) |
$\Theta$(n^2) |
O(n^2) |
O(1) |
| 选择排序 |
$\Omega$(n^2) |
$\Theta$(n^2) |
O(n^2) |
O(1) |
| 树排序 |
$\Omega$(n log(n)) |
$\Theta$(n log(n)) |
O(n^2) |
O(n) |
| 希尔排序 |
$\Omega$(n log(n)) |
$\Theta$(n(log(n))^2) |
O(n(log(n))^2) |
O(1) |
| 桶排序 |
$\Omega$(n+k) |
$\Theta$(n+k) |
O(n^2) |
O(n) |
| 基数排序 |
$\Omega$(nk) |
$\Theta$(nk) |
O(nk) |
O(n+k) |
| 计数排序 |
$\Omega$(n+k) |
$\Theta$(n+k) |
O(n+k) |
O(k) |
| 立方体排序 |
$\Omega$(n) |
$\Theta$(n log(n)) |
O(n log(n)) |
O(n) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| 1. 归并插入排序（Merge Insertion Sort）是一种结合了归并排序和插入排序思想的排序算法。它利用了归并排序在处理大规模数据时的高效性能，同时又利用了插入排序在小规模数据上的优势。
归并插入排序的基本思想是：对于待排序的数组，首先将数组分割成较小的子数组，然后对每个子数组使用插入排序进行排序，最后再使用归并操作将子数组合并成一个有序的数组。
具体步骤如下：
1. 初始状态下，将待排序数组分割成多个较小的子数组（通常是递归地将数组分成两半）。
2. 对每个子数组应用插入排序算法进行排序。当子数组的长度小于等于一定阈值时，切换到插入排序算法。
3. 合并操作：通过不断合并相邻的有序子数组，将子数组合并成一个有序的数组。这一过程类似于归并排序中的合并操作。
归并插入排序的关键在于确定合适的子数组大小，通常当子数组的长度小于一定阈值时，切换到插入排序算法。因为插入排序对于小规模数据具有较好的性能，而归并排序在大规模数据上具有较好的性能。通过合理划分子数组大小，可以在排序过程中充分利用两种排序算法的优势。
归并插入排序算法的时间复杂度为O(n log n)，其中n为待排序数组的长度。由于归并排序和插入排序的时间复杂度都是O(n log n)和O(n^2)级别，归并插入排序在实际应用中的性能与具体实现和问题规模有关。它适用于各种数据分布情况下的排序需求，并且在实践中往往能够提供较好的性能和稳定性。
2. 桶排序（Bucket Sort）是一种排序算法，它将待排序的元素分到不同的桶（或称为容器）中，然后对每个桶中的元素分别进行排序，最后将各个桶中的元素按顺序合并得到有序的结果。
桶排序的基本思想是将待排序的元素均匀地分布到若干个桶中，每个桶内部使用一个较快的排序算法（如插入排序、快速排序等）对元素进行排序。具体的步骤如下：
1. 确定桶的数量和范围：根据待排序元素的分布情况，确定桶的数量，可以是固定的数量，也可以根据元素的范围动态确定。
2. 将元素分配到桶中：遍历待排序的元素，根据元素的值将其分配到相应的桶中。
3. 对每个桶中的元素进行排序：对每个桶内部的元素使用一个较快的排序算法进行排序，可以选择插入排序、快速排序等。
4. 合并桶中的元素：按照桶的顺序，将每个桶中的元素按顺序合并成一个有序的结果数组。
桶排序的时间复杂度取决于分配到桶中的元素的分布情况，以及每个桶内部排序算法的选择。在最理想的情况下，当元素均匀分布在不同的桶中，并且每个桶内部的排序时间复杂度为O(nlogn)时，桶排序的时间复杂度可以达到O(n)。然而，在某些情况下，如果元素分布不均匀，可能会导致较大的空间复杂度或较长的排序时间。
桶排序适用于待排序元素分布较均匀的情况，尤其适合外部排序，即待排序元素无法全部加载到内存中。在实践中，可以根据具体应用场景和数据特点选择合适的桶排序算法的实现方式和参数设置。
3. 立方体排序（Cube Sort），也称为三维排序或多关键字排序，是一种用于对具有多个关键字的记录进行排序的算法。它在三维空间中对记录进行排序，每个记录具有三个关键字，分别对应三个维度。
立方体排序的基本思想是通过多次应用稳定的排序算法，先按照一个维度对记录进行排序，然后按照另一个维度对已排序的记录进行排序，依此类推，直到所有关键字都按照指定顺序排列为止。可以类比为将记录组成一个立方体，按照某个维度逐层进行切割和排序。
具体步骤如下：
1. 确定排序顺序：确定按照哪个维度的关键字先进行排序，然后依次确定其他维度的排序顺序。
2. 应用稳定的排序算法：按照确定的顺序依次对记录进行稳定的排序，通常使用的排序算法有插入排序、冒泡排序、归并排序等。
3. 重复步骤2：对已排序的记录再次按照下一个维度的关键字进行排序，直到所有关键字都按照指定顺序排列。
立方体排序的时间复杂度取决于所使用的稳定排序算法的复杂度和记录的数量。如果记录的数量为n，每个维度的排序所使用的算法复杂度为O(f(n))，那么立方体排序的总时间复杂度为O(d * f(n))，其中d为关键字的维度。
立方体排序适用于多关键字排序的情况，特别适合于具有三个或更多关键字的记录的排序。它可以保持记录之间的相对顺序，并根据每个关键字的重要性进行排序。然而，立方体排序在维度较高和记录数量较大时，可能会面临性能和空间上的挑战。在实际应用中，可以根据具体情况选择合适的排序算法和优化策略。
|
Reference
- Big-O Cheat Sheet
- Splay tree
- K-d tree
- ChatGPT
Gitalking ...