优化数据结构的操作效率。 ‧ 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。 ‧ 支持随机访问：数组允许在 ?(1) 时间内访问任何元素。 ‧ 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓 存来提升后续操作的执行速度。 连续空间存储是一把双刃剑，其存在以下局限性。 ‧ 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。 经常访问的数据和指令，以提高程序运行效率。三者共同协作，确保计算机系统高效运行。 如图 4‑10 所示，在程序运行时，数据会从硬盘中被读取到内存中，供 CPU 计算使用。缓存可以看作 CPU 的 一部分，它通过智能地从内存加载数据，给 CPU 提供高速的数据读取，从而显著提升程序的执行效率，减少 对较慢的内存的依赖。 图 4‑10 硬盘、内存和缓存之间的数据流通 4.4.2 数据结构的内存效率 在内存空间利用方面，数组和链表各自具有优势和局限性。 miss），此时 CPU 不得不从速度较慢的内存中加载所需数据。 显然，“缓存未命中”越少，CPU 读写数据的效率就越高，程序性能也就越好。我们将 CPU 从缓存中成功获 取数据的比例称为缓存命中率（cache hit rate），这个指标通常用来衡量缓存效率。 为了尽可能达到更高的效率，缓存会采取以下数据加载机制。 ‧ 缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行

优化数据结构的操作效率。 ‧ 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。 ‧ 支持随机访问：数组允许在 ?(1) 时间内访问任何元素。 ‧ 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓 存来提升后续操作的执行速度。 连续空间存储是一把双刃剑，其存在以下局限性。 ‧ 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。 经常访问的数据和指令，以提高程序运行效率。三者共同协作，确保计算机系统高效运行。 如图 4‑10 所示，在程序运行时，数据会从硬盘中被读取到内存中，供 CPU 计算使用。缓存可以看作 CPU 的 一部分，它通过智能地从内存加载数据，给 CPU 提供高速的数据读取，从而显著提升程序的执行效率，减少 对较慢的内存的依赖。 图 4‑10 硬盘、内存和缓存之间的数据流通 4.4.2 数据结构的内存效率 在内存空间利用方面，数组和链表各自具有优势和局限性。 miss），此时 CPU 不得不从速度较慢的内存中加载所需数据。 显然，“缓存未命中”越少，CPU 读写数据的效率就越高，程序性能也就越好。我们将 CPU 从缓存中成功获 取数据的比例称为缓存命中率（cache hit rate），这个指标通常用来衡量缓存效率。 为了尽可能达到更高的效率，缓存会采取以下数据加载机制。 ‧ 缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行

优化数据结构的操作效率。 ‧ 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。 ‧ 支持随机访问：数组允许在 ?(1) 时间内访问任何元素。 ‧ 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓 存来提升后续操作的执行速度。 连续空间存储是一把双刃剑，其存在以下局限性。 ‧ 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。 经常访问的数据和指令，以提高程序运行效率。三者共同协作，确保计算机系统高效运行。 如图 4‑10 所示，在程序运行时，数据会从硬盘中被读取到内存中，供 CPU 计算使用。缓存可以看作 CPU 的 一部分，它通过智能地从内存加载数据，给 CPU 提供高速的数据读取，从而显著提升程序的执行效率，减少 对较慢的内存的依赖。 图 4‑10 硬盘、内存和缓存之间的数据流通 4.4.2 数据结构的内存效率 在内存空间利用方面，数组和链表各自具有优势和局限性。 miss」，此时 CPU 不得不从速度较慢的内存中加载所需数据。 显然，“缓存未命中”越少，CPU 读写数据的效率就越高，程序性能也就越好。我们将 CPU 从缓存中成功获 取数据的比例称为「缓存命中率 cache hit rate」，这个指标通常用来衡量缓存效率。 为了尽可能达到更高的效率，缓存会采取以下数据加载机制。 ‧ 缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行

优化数据结构的操作效率。 ‧ 空间效率高: 数组为数据分配了连续的内存块，无须额外的结构开销。 ‧ 支持随机访问: 数组允许在 ?(1) 时间内访问任何元素。 ‧ 缓存局部性: 当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓 存来提升后续操作的执行速度。 连续空间存储是一把双刃剑，其存在以下缺点。 ‧ 插入与删除效率低: 当数组中元素较多时，插入与删除操作需要移动大量的元素。 数 据。然而，我们通常会使用一种更优雅的方式实现堆排序，详见后续的堆排序章节。 ‧ 获取最大的 ? 个元素：这是一个经典的算法问题，同时也是一种典型应用，例如选择热度前 10 的新闻 作为微博热搜，选取销量前 10 的商品等。 8.2 建堆操作 在某些情况下，我们希望使用一个列表的所有元素来构建一个堆，这个过程被称为“建堆操作”。 8.2.1 自上而下构建 我们首先创建一个空堆，然后 出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 ?(?2) ，没有归并排序稳定，但在绝大 多数情况下，快速排序能在 ?(? log ?) 的时间复杂度下运行。 ‧ 缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较 高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。 ‧ 复杂度的常数系数低：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与 “