三向切分快排适用于高重复率（≥30%）数组，通过将元素分为小于、等于、大于基准三段，跳过已有序的中间段递归，使时间复杂度从O(n²)降至接近O(n)。
三向切分在 Go 中不是标准库 sort 的默认行为，但当你面对大量重复元素（比如日志状态码、枚举字段、用户类型 ID）时，手动实现三向切分能显著避免无意义交换，把最坏情况从 O(n²) 降回接近 O(n)。
什么时候必须用三向切分？
当输入数组中存在高比例重复值（例如 ≥30% 元素相同），且你观察到普通快排递归深度异常大、或 sort.Ints 性能明显劣于预期时，就该怀疑是重复元素导致的分区失衡。典型现象包括：
- 对
[]int{2,2,2,2,2,0,0,0,0,0,1,5}排序，普通快排仍会反复将2和2交换 - 基准选中重复值后，
partition返回位置靠近端点，导致子问题规模衰减极慢 -
runtime.GC频繁触发（间接说明栈帧堆积严重）
Go 里怎么写三向切分 partition？
核心是维护三个区间：[lo, lt) 小于 pivot、[lt, gt] 等于 pivot、(gt, hi] 大于 pivot。用两个游标 lt 和 gt 动态收缩相等段，中间指针 i 扫描：
func partition3(a []int, lo, hi int) (lt, gt int) {
pivot := a[lo]
lt, gt = lo, hi
i := lo + 1
for i <= gt {
switch {
case a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt++
i++
case a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt--
// i 不动：刚换过来的 a[i] 还没检查
default: // a[i] == pivot
i++
}
}
return lt, gt
}注意：gt 初始为 hi（闭区间），不是 hi+1；swap 后仅在小于分支推进 i，大于分支不推进——这是防止漏判的关键。
立即学习“go语言免费学习笔记（深入）”；
Golang Uber Dig
下载
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等
递归调用时怎么避开重复段？
三向切分后，[lt, gt] 已天然有序，无需再递归。只对左右两段排序：
- 左段：
quicksort3(a, lo, lt-1) - 右段：
quicksort3(a, gt+1, hi) - 跳过
[lt, gt]—— 这一步省掉的递归调用量，就是重复元素越多收益越大的地方
完整入口函数示例：
func quicksort3(a []int, lo, hi int) {
if lo >= hi {
return
}
lt, gt := partition3(a, lo, hi)
quicksort3(a, lo, lt-1)
quicksort3(a, gt+1, hi)
}
<p>// 使用：
// arr := []int{2,2,2,0,0,1,5}
// quicksort3(arr, 0, len(arr)-1)
和标准库 sort.Ints 比有什么代价？
三向切分逻辑更重，单次 partition3 比内置 sort 的双路切分多一次比较和可能的分支预测失败。所以它只在「重复率高」时净胜出：
- 纯随机数据：三向切分反而慢 5–10%
- 全相同元素：标准
sort.Ints退化为 O(n²)，你的三向版本是 O(n) - 实际业务数据（如订单状态字段只有 3–5 个取值）：建议实测 —— 往往快 2–4 倍
最容易被忽略的是边界处理：Go 切片传参是引用传递，但 lo/hi 是值，递归时若写成 quicksort3(a[lo:gt], ...) 会创建新底层数组，彻底破坏原地性。必须坚持用索引控制范围。
