面试准备中的困难

现在网上随便一搜就能找到一大堆IT岗位的面试题和参考答案，大家也习惯了把这些回答背得滚瓜烂熟。
然而这些内容往往是结论性的解答——只告诉你“该这么做”，却没说清楚“为什么这么做”、“怎么想到要这么做”。或许这就是大家称之为“八股文”的原因吧。
到底该用什么样的思路，才能像那些聪明办法一样，一步一步推导出来、把过程理得清清楚楚？这也是在学习过程中困扰笔者很久的问题。
当然，很多人会觉得“背下来不就得了，想那么多干嘛”、“时间来不及，哪有心思考虑这些”，这倒也是大实话。
不过，要是真想踏踏实实掌握一门技术，做点像样的事情，我还是觉得，理解其背后的原理与逻辑，仍然是不可或缺的。

正因为如此，笔者想试着写这样一篇文章，试着回到每一道题最初的逻辑起点，像拆解俄罗斯套娃一样，一层层追问下去。
这样的过程的确耗费时间，因为每一个问题背后，都可能“递归”般地引出新的为什么。

我们在学C语言的时候，都遇到过这个问题——“数组的下标为什么非要从0开始呢？”
很多人会说“这是规定”，或者“早期设计就这样”。
其实啊，如果我们回到内存本身去想想，数组在内存里其实就是一块连续的空间。假设我们声明了一个数组 $a[10]$ ，那么这块内存的起始地址，我们通常用 $a$ 来表示。这时候，第一个元素的位置，就是 $a$ 本身。第二个元素的位置呢？是$a + 1 \times 元素大小$。第三个呢？$a + 2 \times 元素大小$。

你有没有发现？如果我们把下标从0开始，那么第 $i$ 个元素的地址，就正好是$a + i \times 元素大小$。（当我们说 $a[i]$ 时，这里的 $i$ 是”偏移量”，不是”第几个”。也就是在说“从开头跳过多少个元素”）公式多干净，多整齐！可如果从1开始呢？那就变成$a + (i-1) \times 元素大小$了，每次计算都要多减一个1——对计算机来说，这虽然只是一条指令的事，但在那个内存以KB计算、每条指令都要斤斤计较的年代，这种“不整齐”是让人很难受的。

当然，还有些更深层的原因。比如，指针和数组在C语言里那种若即若离的关系——$a[i]$其实等价于 $*(a + i)$，这种对称的美感，也是从0开始计数才能自然实现的。再往底层想想，CPU的寻址方式是：$\text{基址} + \text{偏移量}$。体现在内存访问上则是：$\text{起始地址} + \text{偏移字节数}$。这也暗示着C语言“贴近硬件”的设计哲学。

写到这儿，自己都觉得有点陷进“递归”里去了。这样一层层追问下去的过程，有时候真的会让人感到疲惫，甚至有点失去耐心。
即便终于来到问题最初的起点，站在了那棵“递归树”的最底层，抬头向上看去，层层叠叠的子问题仿佛看不到尽头。
这时候，你是不是也会有一种“剪不断，理还乱”的混沌感？说实话，写到这里时，我自己也常遇到这种“越想越乱”的时刻。

不过，正是这种抛开所有解题技巧和套路公式，一步一步从事实开始推演的过程，反而让我们能够真正靠自己脑海中的逻辑，慢慢接近问题的本质。这种思考方法，也就是 Elon Musk 先生常提到的第一性原理，也正是我个人非常认同、并且在努力实践的学习方式。
虽然绕了点远路，偶尔也会让人感到迷茫，但最终这样得来的答案，才真正是从自己心里长出来的，也才更贴近“理解”这件事本来的模样吧。

顺带一提，关于数组下标这个话题，笔者之前在自己的CSDN博客里也写过一篇比较详细的梳理，感兴趣的读者可以延伸阅读：数据结构：数组（Array）。

此外，说到《数据结构与算法》这门课，笔者当年是跟着 Abdul Bari 老师的网课一点一点学过来的，感觉受益匪浅。在这里也向 Abdul Bari 老师致敬。关于课程的文字内容，我也做过详细的笔记，读者朋友可以参考：数据结构。

版权与参考声明

本文的主要面试题目和标准答案参考了知名技术博主小林coding。小林老师的内容非常详实，解决了“是什么”的问题；而本文旨在通过第一性原理的视角，探讨这些知识点背后的“为什么”以及如何进行“口语化表达”，帮助读者在面试中不仅能答对，更能“说清”。推荐大家配合小林老师的原作一起食用。

基石：物理存储篇（The Physical Foundation）

探讨内存中数据的最底层形态

包含内容：

  • 数组（Array）：计算机内存可以看作是一把巨大的尺子，有连续的刻度。如果你占用了连续的内存，通过首地址和偏移量，你可以实现“瞬移”。
  • 链表（Linked List）：如果内存碎片化严重，或者我不知道未来要存多少数据，我就不能用数组。链表本质上是“带着地址的包裹”，每个数据都告诉计算机下一个数据在哪里。

1.1 数组和链表的区别是什么？

在计算机底层，数据结构的差异并非来自定义，而是源于计算机内存分配方式与物理寻址机制。通过第一性原理，我们可以从最根本的物理存储特性推导出所有的性能表现。

存储结构的底层差异

数组与链表的根本区别在于：数据在内存中的物理排列方式。

数组的本质是计算机分配了一段连续的、大小固定的内存地址。因为地址是连续的，计算机可以通过一个基础的算术公式直接定位任何元素的物理地址。假设起始地址为 $Base$，单个元素大小为 $size$，那么第 $i$ 个元素的地址就是 $Base + i \times size$。这种物理特性决定了数组具备随机访问的能力。CPU 不需要遍历，只需要执行一次简单的数学运算即可提取数据。

链表的本质是离散内存块的逻辑链接。每一个数据节点（Node）除了存储数据本身，还必须存储一个指向下一个节点地址的指针。在物理上，这些节点分布在内存的随机角落。这种结构意味着计算机无法通过公式计算出某个元素的地址，因为节点之间没有数学上的位置关系。这种物理特性决定了链表必须具备顺序访问的特征。要找到第 $n$ 个元素，物理上必须经过前 $n-1$ 个节点的地址指引。

性能表现的因果推导

基于上述物理结构的差异，我们可以严密推导出两者在操作效率上的不同：

访问操作

  • 数组：由于支持地址直接计算，其访问时间不随数据量增加而改变，复杂度恒定为 $O(1)$。
  • 链表：由于地址不连续，访问必须依赖“寻宝图”式的指针跳转，访问时间随距离线性增长，复杂度为 $O(n)$。

插入与删除操作

  • 数组：受限于“连续空间”的约束，若在中间位置插入元素，为了保持物理地址的连续性，必须将目标位置后的所有数据在内存中整体搬移。这种物理移动导致了 $O(n)$ 的开销。
  • 链表：由于其节点是逻辑解耦的，插入操作仅需修改相邻节点的指针指向。在已知操作位置的前提下，这种修改是原地完成的，不涉及其他节点的移动，效率为 $O(1)$。

硬件视角：被忽视的空间局部性

从更底层的第一性原理——计算机存储金字塔来看，数组在实际运行中往往比链表更快，这源于 CPU 缓存的工作机制。
CPU 每次从内存读取数据时，并非只读取目标字节，而是读取一整行（Cache Line，通常为 64 字节）。

  • 数组：因为内存连续，当 CPU 读取第一个元素时，后续多个元素会被同时加载进缓存。这种高“空间局部性”极大地提升了缓存命中率。
  • 链表：由于节点地址随机，CPU 加载的数据块中很可能不包含下一个节点，导致频繁的缓存失效（Cache Miss），被迫回到主内存读取，性能大幅下降。

面试口语化表达

“我会从物理结构和硬件机制两个层面来看这个问题。

首先，数组的本质是连续内存。这决定了它可以通过下标公式直接计算地址，所以随机访问非常快，是 $O(1)$。但代价是，为了维持连续性，增删操作需要搬移大量数据，效率较低。

其次，链表的本质是离散内存。节点之间通过指针维系逻辑关系，不需要物理上的连续。这使得它在增删时非常灵活，只需要改动指针，不需要移动数据。但缺点是不能随机定位，必须从头遍历，访问效率是 $O(n)$。

最后，从工程实践来看，数组因为内存连续，更符合 CPU 缓存的预读机制，缓存命中率更高；而链表因为节点散乱，容易导致缓存失效。所以，在查多改少的场景下，数组是首选；而在数据量频繁变动且不需要随机访问的场景下，链表更有优势。”

1.2 为什么数组能实现 $O(1)$ 的随机访问？

计算机的内存是一维线性编址的。当我们在高级语言中声明一个数组 $T\ arr[N]$ 时，编译器会向操作系统请求一块连续的、大小为 $N \times \text{sizeof}(T)$ 字节的内存块，并记下其起始地址（基址）。

对于一个存储在连续内存中的元素，其内存地址可以通过一个简单的算术公式确定。设数组的基址为 $base$，每个元素的大小为 $sizeof(T)$，那么第 $i$ 个元素的物理地址为：
$$
address_i = base + i \times sizeof(T)
$$

这个公式就是随机访问的物理基石。CPU要获取 $arr[i]$，只需执行一次乘加运算（$i \times sizeof(T)$）和一次内存寻址（$base + \dots$）。无论 $i$ 是 $0$ 还是 $1000000$，这个计算步骤的数量是固定的，与数组总大小 $N$ 无关。因此，时间复杂度是常数 $O(1)$。

相反，链表节点的内存地址是随机的，节点之间通过指针逻辑相连。要找到第 $i$ 个节点，CPU没有公式可用，必须从第一个节点开始，像拿着一个写着下一个地址的纸条，连续查找 $i$ 次。这个过程所需时间与 $i$ 线性相关，因此是 $O(n)$。

1.3 动态数组（如C++的vector）是如何工作的？

动态数组的“动态”一词容易让人误解。它的物理本质仍然是一块连续的内存。它通过一种精妙的策略来处理容量变化：预分配和复制迁移。

一个动态数组内部通常维护着三个核心信息：

  • 指向一段连续内存的指针 data_；
  • 当前已存储的元素数量 size_；
  • 以及当前已分配内存能容纳的最大数量 capacity_。

当插入新元素且 size_ == capacity_ 时，系统将执行以下物理操作：

  1. 在内存的另一处，申请一块更大的连续空间（通常是原 capacity_ 的 $k$ 倍，$k$ 通常为 2）。
  2. 将原有空间的所有元素，按顺序逐个复制到新空间。
  3. 释放旧的内存空间。
  4. 更新 data_ 指针和 capacity_。

步骤2中的复制操作是昂贵的，时间复杂度为 $O(n)$。然而，如果我们将这次扩容的成本“分摊”到之前所有廉价的插入操作上，平均成本就很低。

采用几何级数扩容（如每次翻倍）时，可以进行均摊分析：假设从1个元素开始，连续插入 $n$ 个元素，触发扩容的总拷贝次数约为 $1 + 2 + 4 + … + \frac{n}{2} < n$。总操作次数少于 $2n$，因此均摊到每次插入的时间复杂度仍然是 $O(1)$。

1.4 双向链表和循环链表解决了什么问题？

单链表每个节点只存储下一个节点的地址（指针）。这个物理设计带来了一个操作上的局限：要删除当前节点，你必须修改“指向它”的那个指针。 而单链表节点本身，并不记录是谁指向了自己。

假设你有一个指向节点 P 的指针，想删除 P。物理上你必须找到 P 的前一个节点 Prev，将 Prev->next 改为 P->next。但在单链表的结构里，你没有 Prev 的信息。唯一的办法是从头开始遍历，直到某个节点的 next 等于 P。这导致单链表“删除已知节点”这个操作本身是 $O(n)$ 的，尽管修改指针本身是 $O(1)$。

双向链表的物理设计选择是：在每个节点里额外存储一个指向前驱节点的指针（prev）。这是一个“用空间换时间”的经典权衡。

空间代价：每个节点多了8字节（64位系统）的 prev 指针开销。

时间收益：当你拥有节点 P 的指针时，你现在可以直接通过 P->prev 获得前驱节点 Prev 的指针。删除 P 的操作变为：

  • P->prev->next = P->next; （让前驱指向后继）
  • P->next->prev = P->prev; （让后继指向前驱）

这两个操作都只需常数时间，无需遍历。于是，“删除已知节点”的整体操作从 $O(n)$ 降为了真正的 $O(1)$。

循环链表的物理设计选择是：将尾节点的 next 指针不设为空（nullptr），而是指向头节点，形成一个闭环。这样做的最大好处是，从链表中的任何一点出发，都可以遍历所有元素，而不用特别关心头尾边界。在某些需要周期性、轮询处理的场景（如操作系统的时间片轮转调度），这个设计消除了对头尾节点的特殊判断，让遍历逻辑更统一。它并没有改变时间复杂度量级，但优化了逻辑的简洁性。

1.5 如何用最简单的物理结构来实现一个高效的LRU缓存？

LRU缓存需要同时满足两个核心操作：

  • 快速查询（get）：给定 key，快速找到对应的 value。这要求类似数组/哈希表，能通过 key 直接定位。
  • 快速维护顺序（put/update）：当访问或更新一个键值对时，需要将其标记为“最近使用”，这涉及到在“使用顺序”这个序列中，快速地将一个节点移动到头部；当缓存满时，需要快速定位并删除“最近最少使用”（尾部）的节点。这要求类似链表，能进行 $O(1)$ 的节点插入和删除。

这里出现了一个物理设计上的根本矛盾：能直接寻址的结构（数组/哈希表）不善于维护动态顺序；善于维护动态顺序的结构（链表）不能直接寻址。

解决矛盾的第一性原理方法是：组合两种物理结构，让它们各司其职。

  • 哈希表 (unordered_map<Key, Node*>)：承担“快速查询”职责。它的物理机制是通过哈希函数将 key 映射到一个数组下标，从而实现 $O(1)$ 的查找。这里它存储的是指向链表节点的指针。
  • 双向链表：承担“维护使用顺序”的职责。链表节点按访问时间排序，头节点是最新访问的，尾节点是最久未访问的。链表支持在已知节点位置时，以 $O(1)$ 速度进行节点的“摘下”和“插入头部”操作。

它们的协作流程完全由物理操作决定：

get(key)：

  1. 哈希表用 $O(1)$ 时间找到对应链表节点的指针。
  2. 通过指针找到节点，将其从链表中摘下（利用其前驱/后继指针）。
  3. 将该节点插入链表头部。
  4. 返回节点中的值。

put(key, value)：

  • 如果 key 已存在，过程类似 get，并更新值。
  • 如果 key 不存在：
    1. 创建新节点，放入哈希表。
    2. 将新节点插入链表头部。
    3. 如果缓存已满（链表长度超过容量）：
    4. 删除链表尾节点（它是LRU）。

同步删除哈希表中以该尾节点 key 为索引的条目。这正是通过尾节点里存储的 key 信息来实现的。

设计图解：

1
2
3
哈希表：      { "A": ptr_A, "B": ptr_B, "C": ptr_C }
                     |         |         |
双向链表： [头] <-> [A:1] <-> [C:3] <-> [B:2] <-> [尾] (最旧)
  • Get(“C”) 后：链表变为 [头] <-> [C:3] <-> [A:1] <-> [B:2] <-> [尾]
  • Put(“D”,4) 且缓存满时：淘汰 B:2，链表变为 [头] <-> [D:4] <-> [C:3] <-> [A:1] <-> [尾]

在这个设计中，让哈希表发挥其基于数组随机访问带来的快速查找优势，让双向链表发挥其离散存储、指针修改快速的顺序维护优势。两者通过共享“节点指针”这一物理内存地址信息进行协同，最终得到一个在满足复杂约束的新结构。

约束：逻辑受限篇（The Logical Constraints）

为什么要在物理基石上限制操作？

包含内容：

  • 栈（Stack）：人类思维中存在大量的“处理完当前的，回去处理上一步”的需求（比如函数调用、括号匹配、撤销操作）。栈不是一种新的物理结构，它是对操作的“管理 规范”，逻辑上只能“先进后出”。目的是为了保证程序执行的确定性。
  • 队列（Queue）：当生产速度大于处理速度时，需要一个缓冲区。“先进先出”，这是社会协作中最公平、最简单的逻辑。队列是解耦生产者和消费者的核心工具，它在操作系统调度、消息中间件中无处不在。

进化：高效索引篇（The Efficiency Evolution）

如何通过改变数据的组织维度，让查询从 O(n) 变成 O(log n) 甚至 O(1)？

包含内容：

  • 哈希表（Hash Table）：如果我们能把任何信息（Key）都瞬间转换成数组下标，那查询就是 O(1)。但是哈希函数计算需要时间，哈希冲突需要处理。
  • 树（Tree）：
    1. 二叉搜索树：本质是二分查找的结构化。每往下走一步，就排除掉一半的可能。
    2. 平衡树（红黑树）：为了防止树退化成链表。它通过复杂的旋转规则，维持搜索的稳定。
    3. B+ 树：针对磁盘 IO 的进化。既然内存连续性在磁盘上很重要，我们就让一个节点多存点数据（多叉），减少“翻页”（IO）次数。
  • 堆（Heap）：如果我只关心最大值或最小值（比如 VIP 排队），我不需要把所有人都排好序，我只需要保证最上面的是我们要的。

3.1 堆的底层为什么总是用数组来实现？

这个问题需要回到两个更基本的物理事实上：第一，堆在逻辑上被定义为一棵完全二叉树；第二，数组在内存中是连续存储的。

完全二叉树有一个至关重要的特性：除了最后一层，其他层都是满的，并且最后一层的节点都尽可能靠左排列。这种规整的结构，使得我们可以用一套简单的数学公式将树中节点与数组下标一一对应。

假设数组下标从0开始：

  • 对于任意下标为 $i$ 的节点，其父节点的下标为 $(i - 1) \div 2$（整数除法）。
  • 其左子节点的下标为 $2 \times i + 1$，右子节点为 $2 \times i + 2$。

这意味着，我们不需要像实现普通二叉树那样，为每个节点动态分配内存并存储左右子节点的指针。我们仅通过一个数组和这三个计算公式，就能在逻辑上完整地描述并遍历这棵树。这种实现方式带来了决定性的优势：

  1. 极致的内存效率：它消除了指针存储的开销（每个节点在64位系统下可节省16字节），所有数据紧密排列，具有极高的空间局部性，对CPU缓存极其友好。
  2. 随机访问能力：我们可以通过下标直接访问树中的任意节点，这是链式存储结构无法做到的。

因此，堆选择数组实现，并非偶然，而是其逻辑定义（完全二叉树）与物理结构（连续数组）相结合的必然选择，目的是为了达到最高的存储和访问效率。

3.2 向堆中插入一个新元素，内部发生了什么？为什么说这个过程是O(log n)的？

插入操作的核心矛盾是：在物理层面，新元素只能被连续地放在数组末尾；但在逻辑层面，新元素必须被安排到满足堆性质（父节点总是大于/小于子节点）的正确位置。解决这个矛盾的算法称为 “上浮”（Shift Up）或“堆化”（Heapify Up）。

我们以最小堆为例，其性质是父节点的值不大于任何一个子节点的值。

物理动作：将新元素放入数组的最后一个位置。这个操作是$O(1)$的。

逻辑修复（上浮）：此时，堆的性质可能在新元素与其父节点之间被破坏。我们需要进行修复：

  • 比较新元素与其父节点的值。
  • 如果新元素的值小于其父节点，那么为了维护最小堆的性质，它们必须交换位置。
  • 交换后，新元素来到了父节点的位置，但可能与新的祖父节点再次冲突。于是，我们将这个过程循环向上进行，就像气泡上浮一样，直到新元素的值不再小于其父节点，或者它已经浮到了树根（数组下标0）。

这个过程的关键在于，每次比较和交换，都发生在一对父子节点之间。最坏情况下，新元素需要从最底层一直上浮到树根。一棵完全二叉树的高度是多少？对于有n个节点的完全二叉树，其高度是 floor(log₂n)。因此，上浮操作最多需要进行与树的高度成正比次数的比较和交换，即 $O(\log n)$ 次。

下面这个简单的C++片段展示了上浮过程的核心循环：

1
2
3
4
5
6
7
8
void shiftUp(int index) {
    while (index > 0) {
        int parent = (index - 1) / 2; // 根据物理索引计算父节点索引
        if (heap[parent] <= heap[index]) break; // 堆性质已满足
        swap(heap[parent], heap[index]); // 交换，修复局部性质
        index = parent; // 继续向上检查
    }
}

3.3 堆排序是如何“就地”完成排序的？

堆排序的全过程，没有为数据分配任何新的存储空间，所有操作都在原始数组内完成。这依赖于数组作为底层存储的两个关键物理特性：连续性和下标计算能力。

第一步：构建初始堆（Heapify）

给定一个无序数组，我们首先要在逻辑上将其“调整”成一个堆。物理上，数组就是我们的存储空间，我们只能通过交换其中元素的位置来达成目的。

  1. 从最后一个非叶子节点开始：这个节点的下标是 n/2 - 1。为什么从这里开始？因为“下沉”操作要有效，必须保证目标节点的左右子树已经是合法的堆。叶子节点没有子节点，天然满足堆性质。所以，我们从最底层的、最小的“子树”开始向上构建，就能确保这个前提。
  2. 进行“下沉”操作：对每个选中的节点，比较它和其左右子节点的值。如果它不满足堆的性质（比如在最大堆中，它比某个孩子小），就将其与更大的孩子交换。然后，这个节点会“下沉”到子节点位置，并可能继续与新的孩子比较和交换，直到它停在满足性质的位置。
  3. 逐步向前：完成一个节点的调整后，我们移动到前一个节点（下标减1），重复这个过程，直到根节点被调整完毕。

这个过程完全在数组内部进行。所有的“下沉”操作，都只是数组中三个元素（父、左子、右子）之间的比较和交换。没有任何数据被复制到新数组，我们只是利用数组的下标计算公式，在逻辑上将其视为一棵树并进行调整。建堆的时间复杂度被证明是 $O(n)$ 。

第二步：反复取出堆顶并调整

此时，数组的第一个元素（堆顶）就是最大（或最小）值，这是堆的性质决定的。

  1. 交换与放置：我们将堆顶元素（$arr[0]$）与当前堆的最后一个元素（$arr[\text{heapSize}-1]$）交换。这个操作完成后，当前堆中的最大值就被物理地放置到了数组的末尾，也就是其排序后的最终位置。
  2. 缩减堆边界：我们将堆的“逻辑大小”减1（$\text{heapSize}–$）。现在，被交换到末尾的最大值被视为已排序部分，不再属于堆。
  3. 修复堆性质：新的堆顶元素（即刚才从末尾交换上来的元素）很可能破坏堆性质。于是，我们对 $arr[0]$ 执行一次 “下沉” 操作。这个操作同样只涉及数组内部元素的比较和交换，并且只在当前的逻辑堆范围内进行。

重复步骤1-3，直到逻辑堆的大小变为1。此时，数组已经是一个有序序列。

为什么说这是“就地”的？

因为在整个过程中，原始数据在数组中的物理位置被不断地重新组织，但从未离开过这个数组。已排序的部分逐渐在数组尾部累积，未排序的堆部分保持在数组头部。我们仅通过几个循环变量和临时交换变量就控制了整个过程，额外的空间复杂度是严格 $O(1)$。

3.4 堆排序的优势与代价

从上述物理过程，我们可以直接推导出它的优缺点。

优势

  • 时间复杂度稳定：无论输入数据是正序、逆序还是随机，堆排序的时间复杂度都是 $O(n \log n)$。这是因为建堆是$O(n)$，而$n-1$次“下沉”操作，每次都是$O(\log n)$。它没有快速排序那种可能退化为$O(n^2)$的最坏情况。
  • 空间复杂度极低：它是严格的原地排序算法，只需要常数级别的额外空间。这在内存受限的环境（如嵌入式系统）中是一个重要优点。

代价

  • 缓存不友好（这是最重要的实际代价）：现代CPU依赖缓存来加速内存访问。缓存更擅长连续访问（空间局部性）。堆排序在排序阶段的主要操作是：访问 $arr[0]$（堆顶），然后访问 $arr[\text{heapSize}-1]$（堆尾），交换它们，再对 $arr[0]$ 进行下沉。下沉过程中，对节点的访问是根据下标计算公式 跳跃式 进行的（从父节点跳到左子或右子）。这种从数组头部到尾部、再到中间某处的非连续内存访问模式，会导致大量的缓存未命中（Cache Miss）。相比之下，快速排序或归并排序的访问模式更为连续。因此，尽管堆排序的理论复杂度优秀，但在实际硬件上运行通常比快速排序慢。
  • 不稳定：排序算法的“稳定性”是指相等的元素在排序后保持原有的相对顺序。在堆排序中，进行“交换堆顶与堆尾”以及“下沉”操作时，原本位于后面的相等元素可能会因为被交换到堆顶并下沉，而跑到另一个相等元素的前面。因此，堆排序是一种不稳定的排序算法。