三路快排通过将数组分为小于、等于、大于pivot三段，使重复元素集中于中间段不再参与递归，避免Lomuto分区在重复元素下的O(n²)退化；配合随机化pivot选择和边界校验，可确保平均O(n log n)性能与稳定性。
partition 函数对重复元素的敏感性
标准 Lomuto 分区（比如用 arr[high] 当 pivot，然后单向扫描）在大量重复元素时会退化：所有相等元素都堆在一边，导致左右子数组极不均衡。最坏情况下递归深度变成 O(n)，时间复杂度飙升到 O(n²)。
这不是 bug，是分区逻辑本身的设计局限 —— 它只保证「≤ pivot 在左，> pivot 在右」，没做等值分离。
- 输入
[]int{5, 5, 5, 5, 5, 1, 9}，pivot = 5，扫完后可能只剩[1]和[5,5,5,5,5,9]两块 - 下一轮又选 9 当 pivot，再分出
[5,5,5,5,5]……无限接近链状递归 - Go 运行时栈深度有限，大数据量下容易触发
runtime: goroutine stack exceeds 1000000000-byte limit
改用三路快排（Dutch National Flag）
核心是把数组切成三段：｜== pivot｜> pivot。重复元素全挤进中间段，不再参与后续递归 —— 这直接砍掉重复值带来的冗余调用。
Go 里实现关键是维护三个指针：lt（小于区右边界）、gt（大于区左边界）、i（当前扫描位）。边扫边交换，无需额外空间。
func quickSort3way(arr []int, lo, hi int) {
if lo >= hi {
return
}
pivot := arr[lo]
lt, gt := lo, hi
i := lo + 1
for i pivot {
arr[i], arr[gt] = arr[gt], arr[i]
gt--
// i 不动：换过来的 arr[i] 没检查过
} else {
i++
}
}
quickSort3way(arr, lo, lt-1)
quickSort3way(arr, gt+1, hi)
}
- 注意
arr[i] > pivot分支里没执行i++，这是关键：刚从右边换来的值必须重新判断 - 基准选
arr[lo]比arr[hi]更稳，避免末尾重复值集中导致初始gt偏移
基准值随机化防最坏输入
即使用了三路分区，如果输入是人工构造的极端重复序列（比如全部相同），且你总选首/尾当 pivot，递归依然会深达 O(n)。必须打破确定性。
Golang Uber Dig
下载
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等
在每次递归前，把随机位置的元素和 arr[lo] 交换 —— 这让攻击者无法预判 pivot 位置，平均性能回归 O(n log n)。
- 加一行：
rand.Seed(time.Now().UnixNano())（仅需一次，放 main 开头） - 分区前插入：
r := lo + rand.Intn(hi-lo+1); arr[lo], arr[r] = arr[r], arr[lo] - 别用
math/rand的全局 Seed，高并发下会竞争；真要并发安全，用rand.New(rand.NewSource(time.Now().UnixNano()))
切片传递与原地排序的边界陷阱
Go 切片是引用头 + 长度 + 容量，但 arr[:lt-1] 这种操作如果 lt == lo，会导致 arr[: -1] panic —— 这类越界在重复元素多时更容易暴露。
务必在递归调用前校验索引有效性：
if lt > lo { quickSort3way(arr, lo, lt-1) }if gt- 不要依赖
len(arr) 就 return：三路分区后子区间可能为空，但索引已非法
最麻烦的是，这种 panic 不一定在第一层出现，可能压栈十几层后才崩，调试时得打日志看 lo/hi 实际值。
golang免费学习笔记（深入）：立即使用
在学习笔记中，你将探索golang的核心概念和高级技巧！
