OI-wiki 基础算法篇：Timsort 混合稳定排序算法深度解析

OI-wiki 基础算法篇Timsort 混合稳定排序算法深度解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读Timsort 是一种由 Python 核心开发者 Tim Peters 于 2002 年设计的混合稳定排序算法它巧妙结合了插入排序与归并排序的优点针对数据集中天然存在的部分有序特性进行了精确优化因而特别适合处理包含大量有序子序列的真实数据。本文以 docs/basic/tim-sort.md 为主体结合仓库中 插入排序、归并排序 与 排序算法总览 等相邻章节系统讲解 Timsort 的 Run 识别、Run 扩展、栈式归并与加速模式等核心机制并给出完整的复杂度证明与伪代码实现帮助读者理解 Python、Java 等语言默认排序背后的工作原理。引入为什么需要 Timsort在 Timsort 出现之前常见的排序算法各有短板快速排序在部分有序数据上容易退化插入排序对小规模数据高效但整体复杂度为 $O(n^2)$归并排序稳定但常数较大。Timsort 的设计初衷就是识别并利用数据集中已有的有序性——真实世界中的数据如日志记录、用户列表往往并非完全随机而是包含大量已排序的连续片段。Timsort 由 Python 核心开发者 Tim Peters 于 2002 年设计并应用于 Python 语言自 Python 2.3 版本起被选为 Python 标准库的默认排序算法此后也被广泛应用于其他编程环境例如在 Java SE 7 中用于对非原始对象数组进行排序。从仓库的排序章节结构看Timsort 属于基于比较的稳定排序家族。正如 排序算法总览 所述稳定性是指相等的元素经过排序之后相对顺序是否发生了改变而归并排序、插入排序均属稳定排序——Timsort 正是以这两者为基石的混合体。仓库 基础算法目录 也将本章内容定位为足够优美及趣味性在之后的进阶内容中也常常会出现的基础算法。算法总流程识别、扩展、归并三步走Timsort 的核心思想是通过识别和利用数据集中已有的有序性来提高排序效率其主要包括以下步骤识别 Run扫描待排序数组识别出有序的连续子序列Run。扩展 Run如果识别的 Run 长度小于MIN_RUN则使用插入排序对其进行扩展。归并 RunTimsort 维护一个特殊的栈采用特定的归并策略将栈中已有的 Run 合并成更大的有序序列。识别 Run首先Timsort 会从左向右扫描数组识别出连续的有序序列这些有序序列被称为 Run升序 Run如果后一个元素大于等于前一个元素则继续扩展 Run。降序 Run如果后一个元素小于前一个元素则继续扩展 Run随后将该 Run 反转为升序。这里值得注意两点其一升序 Run 判定使用的是大于等于即允许相邻相等元素共存于同一 Run这与 归并排序 中为保证稳定性而采用a[i] b[j]而非a[i] b[j]的取舍一脉相承其二降序 Run 会被整体反转使得栈中保存的 Run 一律为升序从而统一后续归并的处理逻辑。扩展 Run二分插入排序补齐到 MIN_RUN为了提高小规模数据的排序效率Timsort 引入了一个 Run 的最小长度MIN_RUN。其值一般根据待排序数组的长度动态计算通常为 $32$ 至 $64$ 之间。如果识别的 Run 长度大于等于MIN_RUN则不需要额外操作直接将 Run 压入栈中。如果识别的 Run 长度小于MIN_RUN则使用二分插入排序将该 Run 的后续元素插入到 Run 中直到 Run 的长度达到MIN_RUN然后将其压入栈中。二分插入排序正是仓库 插入排序 中折半插入排序一节所述的技术通过二分查找仓库中使用upper_bound确定插入位置后再用memmove批量移动元素。折半插入排序与直接插入排序的基本思想一致只是对常数进行了优化时间复杂度不变——这正是 Timsort 在大规模排序中使用它的理由扩展 Run 的长度被限制在MIN_RUN不超过 64此时 $O(k^2)$ 的插入排序在常数很小的前提下完全可控且相比归并操作开销更低。归并 Run用栈管理平衡的归并在 Timsort 中归并排序是通过栈来管理和控制的。栈中保存了已经识别出的有序 Run并通过特定的归并规则控制栈中 Run 的合并其目的是在合并时保持序列的平衡性和稳定性。归并规则稳定性与平衡性双保证Timsort 是一种稳定的排序算法即相同元素在排序后仍然保持原有的相对顺序。为确保这一点Timsort 在归并时只会合并相邻的、连续的 Run而不会直接合并非相邻的 Run——因为非相邻的 Run 之间可能存在相同的元素直接合并很可能会打乱它们的相对顺序。同时为了确保合并的平衡性Timsort 引入了特定的归并规则。在每次合并操作之前算法会检查栈顶的三个 Run X、Y 和 Z以确保满足以下两个条件条件一len(Z) len(Y) len(X)条件二len(Y) len(X)如果栈顶的三个 Run 不满足上述条件Timsort 会将 Y 与 X 或 Z 中较小的一个进行合并然后再次检查条件。一旦条件满足则开始继续搜索新的 Run将其添加到栈中并开始下一轮的归并。这两个条件可以直观理解为栈中 Run 的长度自底向上大致呈非严格递减且任意三层都满足下层能包住上层之和。这保证了合并是延迟的、按需的——只有出现长度失衡时才触发合并从而让各次归并的代价保持均衡避免出现某次归并一方 Run 极小、另一方极大导致的低效。归并优化二分定位 临时缓冲区为了在归并不同长度的 Run 时提高效率并减少空间开销Timsort 在归并前会通过二分查找精确定位需要处理的元素范围只对需要移动的部分进行归并具体方式为确定插入点使用二分查找找到第二个 Run 的第一个元素在第一个 Run 中的插入位置以及第一个 Run 的最后一个元素在第二个 Run 中的插入位置。这样可以缩小需要归并的范围只对需要移动的元素进行处理。临时缓冲区传统的原地合并算法效率太低需要大量的元素移动。为了减少这种开销Timsort 使用一个临时缓冲区将长度较小的 Run 复制到缓冲区中然后逐步将元素从缓冲区复制回原数组。例如假设存在两个 Run A 和 B分别为Run A$[1, 2, 3, 6, 10]$Run B$[4, 5, 7, 9, 12, 14, 17]$通过二分查找可以确定元素 $4$ 应插入到 Run A 的第四个位置元素 $10$ 应插入到 Run B 的第五个位置。因此Run A 的前 $3$ 个元素和 Run B 的后 $3$ 个元素已经在正确位置无需处理。只需归并 Run A 的 $[6, 10]$ 和 Run B 的 $[4, 5, 7, 9]$其归并过程如下图所示从示意图可以看到归并时只需把较小的 Run即数据较少的 $[6, 10]$复制进临时内存缓冲区随后将另一侧的元素依次归并回原数组——这与 归并排序 中使用与原数组等长的辅助数组的经典做法相比显著减少了辅助空间与移动开销。加速模式Galloping Mode 与动态阈值为进一步提升归并效率Timsort 引入了加速模式Galloping Mode。在标准的归并过程中算法会逐一比较两个 Run 中的元素将较小的元素放入结果数组。然而如果一侧的 Run 中有大量连续元素比另一侧的当前元素要小逐一比较会造成不必要的开销。为了解决这一问题Timsort 设定了一个阈值Min_Gallop默认值为 $7$。当一侧 Run 中的元素连续比较胜利的次数达到Min_Gallop时算法会进入加速模式快速定位元素位置其具体步骤如下指数查找从当前位置开始算法以指数增长的步长 $(1, 2, 4, 8, \dots)$ 在一侧的 Run 中查找直到找到一个区间使得目标元素位于该区间内。二分查找一旦确定了包含目标元素的区间算法会在该区间内使用二分查找精确定位目标元素的位置。通过这种方式Timsort 可以跳过大量不必要的比较快速处理一侧 Run 中连续的、较小或较大的元素将它们批量移动到合并结果中。然而加速模式并非在所有情况下都更高效。在某些数据分布下加速模式可能导致更多的比较次数。为此Timsort 采用了动态调整策略阈值调整维护一个可变的Min_Gallop参数。当加速模式表现良好即连续多次从同一 Run 中选取元素时Min_Gallop减 $1$鼓励继续使用加速模式当加速模式效果不佳频繁在两个 Run 之间切换时Min_Gallop加 $1$降低加速模式的使用频率。通过动态调整Min_Gallop的值算法能够根据实际数据情况在普通归并模式和加速模式之间取得平衡。对于部分有序或高度有序的数据加速模式可以显著提高效率使 Timsort 的性能接近 $O(n)$而对于随机数据算法会逐渐倾向于使用普通归并从而保证 $O(n \log n)$ 的时间复杂度。复杂度分析Timsort 的时间复杂度取决于数据的有序性最优情况$O(n)$——当数据已经有序或近似有序时算法识别出的 Run 长度接近 $n$归并次数减少复杂度趋近于 $O(n)$。最坏情况$O(n \log n)$——在数据完全无序的情况下每一个 Run 的长度都接近 $1$因此需要 $O(\log n)$ 次归并每次归并的代价为 $O(n)$总复杂度为 $O(n \log n)$。证明识别和扩展 Run识别 Run 需线性遍历一次数组其复杂度为 $O(n)$。使用插入排序扩展 Run 也需线性遍历数组其复杂度为 $O(n)$。归并 Run归并操作的总次数与 Run 的总数有关最坏情况下 Run 的数量为 $n / \text{MIN_RUN}$由于MIN_RUN是常数因此 Run 的数量可看作 $O(n)$。$O(n)$ 个 Run 需要进行的归并次数为 $O(\log n)$每次归并操作的代价为 $O(n)$因此归并操作的总复杂度为 $O(n \log n)$。而对于空间复杂度由于 Timsort 大致需要额外的 $O(n)$ 空间用于存储栈和临时缓冲区因此总的空间复杂度为 $O(n)$。作为对照排序算法总览 指出基于比较的排序算法的时间复杂度下限是 $O(n\log n)$——Timsort 的最坏情况恰好达到了这一理论下界同时又在最优情况下突破到线性这正是其自适应价值的体现。实现伪代码全流程以下伪代码完整展示了 Timsort 的主循环逻辑摘自 docs/basic/tim-sort.md$$ \begin{array}{ll} 1 nRemaining \gets \text{数组长度} \ 2 minRun \gets \text{选择合适的 MinRun 的值}(nRemaining) \ 3 startIndex \gets 0 \ 4 \textbf{while } nRemaining 0 \ \textbf{do} \ 5 \qquad runLength \gets \text{识别 Run }(array, startIndex, nRemaining) \ 6 \qquad \textbf{if } runLength minRun \ \textbf{then} \ 7 \qquad \qquad extendLength \gets \min(minRun, nRemaining) \ 8 \qquad \qquad \text{使用插入排序扩展区间 } [startIndex, startIndex extendLength - 1]\ 9 \qquad \qquad runLength \gets extendLength \ 10 \qquad \textbf{end if} \ 11 \qquad \text{将 Run } (startIndex, runLength) \text{ 压入栈中} \ 12 \qquad \textbf{调用 } \text{mergeCollapse(栈)} \ \text{检查并合并栈中的 Run } \ 13 \qquad startIndex \gets startIndex runLength \ \text{更新起始位置} \ 14 \qquad nRemaining \gets nRemaining - runLength \ \text{更新剩余长度} \ 15 \textbf{end while} \ 16 \textbf{调用 } \text{mergeForceCollapse(栈)} \ \text{对栈中所有 Run 进行最终的合并} \ \end{array} $$对照前文的机制讲解可以逐一对应伪代码中的关键环节第 2 行根据剩余长度动态计算minRun即MIN_RUN通常取 $32 \sim 64$对应扩展 Run一节第 5 行识别 Run对应识别 Run一节含降序反转第 610 行在 Run 过短时用插入排序补齐到minRun第 1112 行压栈并调用mergeCollapse后者内部实现了归并规则一节的栈顶三元素检查与条件触发合并第 16 行在全部 Run 入栈后调用mergeForceCollapse做最终的强制归并将所有 Run 合并为完整有序数组——此阶段的归并同样享受二分定位、临时缓冲区与加速模式三项优化。总结与延伸阅读Timsort 的成功在于三点设计上的对症下药识别 Run把数据中已有的有序性直接转化为可复用资产栈式归并规则len(Z) len(Y) len(X)与len(Y) len(X)在保证稳定性的前提下维持归并的平衡性加速模式与动态Min_Gallop则让算法在批量跳跃与逐元素比较之间自适应切换。三者叠加使得 Timsort 在部分有序数据上逼近 $O(n)$在随机数据上保持 $O(n \log n)$空间复杂度为 $O(n)$。若希望进一步夯实排序基础可继续阅读仓库中的相关章节插入排序与折半插入排序——Timsort 扩展 Run 所依赖的基础算法归并排序——Timsort 归并阶段的算法原型可对照理解稳定性保证与辅助数组的使用排序算法总览——稳定性、时间复杂度、空间复杂度等排序性质的统一界定排序的用途 与 二分查找——理解排序作为查找预处理的实际价值标准库排序——对比 C/C 标准库中qsort、std::sort等其他排序实现。本文基于仓库 docs/basic/tim-sort.md 编写并交叉参考了同目录下排序相关章节文中图片 tim-sort-1.png 与 tim-sort-2.apng 均取自该页面的原始素材。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考