夜雨聆风
Java源码中的排序算法(七)-TimSort之Galloping 模式
之前已经分享了3篇关于TimSort的内容，今天继续
你有没有想过，为什么 Collections.sort() 在处理“几乎有序”的数据时快得惊人？
答案藏在 Timsort 的一个精妙优化中——Galloping 模式。
一、什么是 Galloping 模式？
Galloping模式命名简单粗暴，直抒胸臆，gallop本身就是飞奔的意思。是 Timsort 在归并两个有序片段（run）时，用于加速“一边倒”场景的智能策略。
想象合并两列已排序的队伍：
-
A 队： [1, 3, 5, 7, 9, ..., 99] -
B 队： [100, 102, 104, ...]
普通归并会逐个比较 50 次，而 Galloping 能一眼看出“A 全小于 B”，直接批量移动——从 O(n) 比较降到 O(log n)！
二、核心功能：批量跳过，减少比较
目标
当一个 run 的多个连续元素都小于（或大于）另一个 run 的当前元素时，快速定位可批量移动的边界，避免逐个比较。
触发条件
-
连续 MIN_GALLOP（默认 7）次“一边倒”比较
（例如：A 的元素连续 7 次 < B 的头部）
三、关键逻辑 + JDK 21 源码示例
Galloping 分两步走，我们结合 JDK 21 TimSort.java 源码来看：
步骤 1：指数跳跃（找大致范围）
// TimSort.java - gallopRight 方法片段
int lastOfs = 0;
int ofs = 1;
while (ofs < len && c.compare(a[base + ofs], key) < 0) {
lastOfs = ofs;
ofs = (ofs << 1) + 1; // 指数增长: 1 → 3 → 7 → 15...
if (ofs <= 0) ofs = len; // 防整数溢出
}
if (ofs > len) ofs = len;
作用：快速跳过连续小于
key的区域，找到上界ofs和下界lastOfs。
步骤 2：二分查找（精确定位）
// 在 [lastOfs, ofs) 区间内二分查找第一个 >= key 的位置
int result = lastOfs + binarySearch(a, base + lastOfs, base + ofs, key, c);
其中 binarySearch 是标准二分查找实现。
总比较次数 ≈ 2·log₂(k)（k 为实际可移动长度）
普通归并需 k 次比较
例：k=1000 → Galloping 约 20 次 vs 普通 1000 次！
步骤 3：动态调整阈值（越用越聪明）
// mergeLo/mergeHi 中的自适应逻辑
if (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP) {
// 成功找到长序列 → 降低下次触发门槛
minGallop = Math.max(MIN_GALLOP, minGallop - 1);
} else {
// 失败 → 提高门槛，避免无效切换
minGallop++;
}
智能反馈：让 Galloping 只在真正有效时启用。
四、对 Timsort 的作用：自适应性能的关键
|
|
|
|
|---|---|---|
|
|
|
|
|
|
|
减少 30%~50% 比较 |
|
|
|
减少 40%~60% 比较 |
|
|
|
O(log n) 比较 |
核心价值：在真实业务数据（如时间序列、ID 递增）上，显著提升性能，而对随机数据零惩罚。
五、与其他方法对比
|
|
|
|
|
|
|---|---|---|---|---|
| 普通归并 |
|
|
|
|
| 纯二分归并 |
|
|
|
|
| Galloping |
|
自适应
|
|
真实数据 |
Galloping 的优势：
不是“永远用高级方法”，而是“该用时才用” 动态调整阈值（ minGallop），越用越聪明
六、总结
Galloping 模式是 Timsort 工程智慧的缩影：
-
尊重现实：真实数据常有“一边倒”结构； -
智能切换：仅在收益 > 成本时启用； -
高效定位：指数跳跃 + 二分，兼顾速度与精度。
下次当你调用 list.sort() 时，不妨想想：背后可能正有一匹“骏马”在数据草原上飞奔，为你省下成千上万次无谓的比较。
💡 感谢你看完这篇内容，这是我自己在工作学习中遇到的case，做一些简单的 究，并总结经验，如有遗漏或不合理的地方，欢迎你提出问题，让我们一起探索。
