- 正确答案：双分割器（Double Pivot Partitioning）是快速排序的一种改进分区策略，它在一次划分过程中选取两个基准值（pivot1 和 pivot2），将数组划分为三个区间：小于 pivot1 的部分、介于 pivot1 和 pivot2 之间的部分（含等于）、大于 pivot2 的部分。通常要求 pivot1 ≤ pivot2，常见做法是令 pivot1 = min(arr[left], arr[right])，pivot2 = max(arr[left], arr[right])，或通过三数取中后选最小和最大作为双枢轴。 - 解答思路：双分割器的核心目标是减少递归深度、提升缓存局部性、降低重复元素处理开销（尤其对含大量重复值的数组）。其划分过程需维护三个指针（或四个边界）： • low 区间右边界（< pivot1） • mid 区间右边界（∈ [pivot1, pivot2]） • high 区间左边界（> pivot2） • 一个扫描指针 cur 在 [low+1, high−1] 范围内遍历。每次根据当前元素 x 与两个 pivot 的比较结果，决定将其归入哪一区间，并通过交换操作动态调整三区边界。整个过程仅需一次扫描（O(n) 时间），且不依赖额外空间（原地划分）。 - 深度知识讲解：双分割器是“双轴快排”（Dual-Pivot Quicksort）的基石，被 Java 7+ 的 Arrays.sort(int[]) 默认采用（由 Vladimir Yaroslavskiy 提出并优化）。其理论优势在于： • 平均比较次数比单轴快排减少约 5–10%，因每次划分产生三个子问题而非两个，期望递归深度为 log_{3/2} n ≈ 1.71 log₂n，优于单轴的 2 ln n ≈ 1.39 log₂n？——注意：此处需澄清：实际期望递归深度仍为 O(log n)，但底数更大（3/2 > e^{1/2}），意味着更平衡的子问题规模分布；更关键的是，其比较次数期望为 ~1.40 n ln n（单轴为 ~1.39 n ln n），但因分支预测友好、缓存命中率高、且对重复元素天然鲁棒，实测性能显著提升。 • 对重复元素具有天然稳定性：当 pivot1 == pivot2（即两基准相等）时，算法自动退化为三路划分（Dutch National Flag），将所有等于 pivot 的元素集中于中段，避免了重复元素导致的最坏 O(n²) 退化。 • 底层实现依赖“四指针法”（four-pointer scheme）：经典 Yaroslavskiy 分区使用 left、right、less、great 四个索引（JDK 实现中为 lt, gt, i, j），其中： - lt 初始为 lo，指向 < pivot1 的右边界； - gt 初始为 hi，指向 > pivot2 的左边界； - i 从 lo+1 开始向右扫描，j 从 hi−1 开始向左扫描； - 根据 arr[i] 和 arr[j] 与两个 pivot 的关系，执行不同交换逻辑（如 arr[i] < pivot1 → 与 arr[lt] 交换，lt++，i++；arr[i] > pivot2 → 与 arr[gt] 交换，gt--，但 i 不增；arr[i] ∈ [pivot1,pivot2] → i++）。该方案避免了嵌套 if 判断，利于 CPU 流水线执行。关键底层知识点： • 原地划分的不变式（invariant）设计：始终维持 arr[lo+1 .. lt] < pivot1，arr[lt+1 .. i−1] ∈ [pivot1, pivot2]，arr[j+1 .. gt−1] ∈ [pivot1, pivot2]，arr[gt .. hi] > pivot2。该不变式是正确性的数学基础。 • 分支预测敏感性：Yaroslavskiy 算法将多数判断集中于 i/j 与 pivot 的比较，并尽量保证高频路径（如中段元素）不触发跳转，从而提升现代 CPU 的分支预测准确率。 • 内存访问模式：相比单轴快排的“一前一后”双向扫描，双轴采用“内外夹逼”扫描（i 向右、j 向左），局部性更好，L1 cache miss 率更低。 - 伪代码（Yaroslavskiy 双轴分区，升序，输入 arr[lo..hi]，返回两个分割点 p, q，满足 arr[lo..p−1] < pivot1 ≤ arr[p..q] ≤ pivot2 < arr[q+1..hi]）： ``` function dualPivotPartition(arr, lo, hi): if arr[lo] > arr[hi]: swap arr[lo] and arr[hi] pivot1 = arr[lo] pivot2 = arr[hi] lt = lo + 1 gt = hi - 1 i = lt while i <= gt: if arr[i] < pivot1: swap arr[i] and arr[lt] lt++ else if arr[i] > pivot2: while arr[gt] > pivot2 and i < gt: gt-- swap arr[i] and arr[gt] gt-- if arr[i] < pivot1: swap arr[i] and arr[lt] lt++ i++ lt-- gt++ swap arr[lo] and arr[lt] swap arr[hi] and arr[gt] return lt, gt ``` 注：上述伪代码为简化教学版；JDK 实际实现更精巧，使用 do-while 循环避免边界检查冗余，并严格维护循环不变式。真实源码可见 java.util.DualPivotQuicksort.partition() 方法。 - 扩展知识：双分割器是“多轴快排”（Multi-Pivot Quicksort）的特例（k=2）。理论上 k 越大，划分越细，但 k 增大会导致比较次数上升（每元素需比较 k 次）、分支复杂度剧增、缓存失效加剧，实证表明 k=2 是性能拐点。此外，双轴思想也被用于快速选择（Quickselect）、外部排序缓冲区管理、以及数据库中的范围分区（Range Partitioning）优化。理解双分割器，本质上是在掌握如何用有限状态机协同多个指针，在单次遍历中完成多类数据的归类——这是所有原地分治算法（如三路快排、堆化、BFPRT 中的 median-of-medians 分组）共通的底层范式。

老牌中厂一面

全站热榜

创作者周榜