双轴快排 Dual-Pivot Quicksort

交换排序 · 快排变体 · Java Arrays.sort 实际采用

从一根轴到两根轴

普通快排一趟围着一个基准把数组劈成两段。2009 年 Yaroslavskiy 提出：一趟干脆用两个基准（p ≤ q），把数组直接分成三段——< p / [p, q] / > q。段分得更碎、递归更浅，配合更少的元素搬动和更好的缓存局部性，实测普遍快过单轴快排——Java 7 起基本类型的 Arrays.sort 用的就是它。

双轴快排怎么做

取区间首尾两个元素当双基准：若 a[lo] > a[hi] 先交换两端，保证 p ≤ q（下面第 2、3 趟就会看到这一步）。然后还是熟悉的三指针 lt / i / gt 扫描中间：a[i] < p 就和 lt 交换、两者右移；a[i] > q 就和 gt 交换、gt 左移（i 不动，换来的值还没查）；落在 [p, q] 之间就留在中段、i 右移。扫描完把两个基准分别换到三段的交界处——p 归位到左段右侧、q 归位到中段右侧，这两个位置直接钉死，再对剩下的三段分治。

下面固定 8 个数 [3, 5, 9, 1, 6, 2, 4, 7]。点「下一步」：首趟双基准 p=3、q=7（两根紫柱），一趟扫出 [2,1] | 3 | [5,6,4] | 7 | [9]——双基准归位钉死后，只剩左右两个小段进区间栈。留意第 2、3 趟弹出的子区间首尾是反的，都要先交换两端再选双基准。

复杂度与为什么 Java 选它

平均 O(n log n)、原地、不稳定，和单轴快排同级。优势在常数：一趟分三段让递归树更浅（约 log₃ 级），元素跨段搬动更少、访存更连续。Yaroslavskiy 的基准测试赢了当时 JDK 的单轴实现，于是 Java 7 把基本类型的 Arrays.sort 换成了它（工程版还叠加了五点取样选轴、小段转插入排序等细节，本页取首尾双基准展示主线）。

它和三路快排是一对好对照：同样的 lt/i/gt 三指针、同样「一趟三段」，一个靠「等于」收中段、一个靠「第二根轴」撑中段。两页对着单步走一遍，三指针划分这个技巧就吃透了。