Golang快速排序怎么使用三向切分优化-Golang-PHP中文网

三向切分快排适用于高重复率（≥30%）数组，通过将元素分为小于、等于、大于基准三段，跳过已有序的中间段递归，使时间复杂度从O(n²)降至接近O(n)。

golang快速排序怎么使用三向切分优化

三向切分在 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  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，大于分支不推进——这是防止漏判的关键。

递归调用时怎么避开重复段？

三向切分后，[lt, gt] 已天然有序，无需再递归。只对左右两段排序：

Golang Uber Dig

使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等

下载

左段：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)
</p>