选错 pivot 会导致快速排序退化为 O(n²)，尤其在已排序数组上；Go 的 sort.Ints 使用 pdqsort 而非纯快排；用末元素作 pivot 最简但最危险，升序时递归深度达 n 层。
选错 pivot 会导致快速排序退化成 O(n²)，尤其在已排序或近乎有序数组上。Golang 没有内置快排实现（sort.Ints 用的是优化过的 pdqsort，不是纯快排），所以自己写时，pivot 策略必须手动控制。
用最后一个元素做 pivot 最简单但最危险
这是教科书式写法，代码简洁，但遇到升序数组会触发最坏时间复杂度。比如对 []int{1,2,3,4,5} 排序，每次 pivot 都是最大值，分区后左子数组长度为 n−1，右子数组为空，递归深度达 n 层。
- 适用场景：数据完全随机、且规模很小（
- 风险点：无法抵抗恶意输入或日志类时间序列数据（天然接近有序）
- 示例写法：
pivot := arr[len(arr)-1]，后续用双指针分区
用中间索引元素（arr[len(arr)/2]）更鲁棒
比首/尾元素抗干扰强，尤其对部分有序数组效果明显。Golang 社区很多教学实现默认采用这个策略，因为它不依赖数据分布，也不需要额外随机数生成开销。
- 注意：取中位索引不等于取中位数，只是位置居中；若数组长度为偶数，
len(arr)/2是向下取整，没问题 - 缺点：仍可能被构造数据攻击（如把中间位置故意设为极值）
- 实操建议：配合三数取中（见下一条）可进一步提升稳定性
三数取中（median-of-three）是生产级首选
取首、中、尾三个位置的元素，排序后选中间值作为 pivot。它大幅降低最坏情况概率，且开销极小（仅两次比较 + 一次交换）。
Golang Uber Dig
下载
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等
立即学习“go语言免费学习笔记（深入）”；
- 典型实现顺序：
low、mid、high三处取值 → 排序这三个数 → 把中位数换到high位置 → 再调用标准分区逻辑 - 优势：对已排序、逆序、重复多的数组都表现稳健；Go 标准库的
pdqsort在切换到快排分支前就用了类似策略 - 坑点：别在
len(arr) 时还硬算三数——要加长度保护，否则越界 panic
随机选取 pivot 要谨慎使用
理论上能避免最坏情况，但 Go 的 rand.Intn 默认未 seed，多次运行可能返回相同序列；而且伪随机本身有周期性，在高频排序场景下反而引入不可预测抖动。
- 如果真要用，务必在程序启动时调用
rand.Seed(time.Now().UnixNano()) - 更轻量的做法：用当前 goroutine ID 或指针地址哈希（如
uintptr(unsafe.Pointer(&arr[0])) % len(arr)），避免依赖全局 rand 状态 - 不推荐在性能敏感路径（如实时流处理）中用
rand，函数调用和锁开销比三数取中高得多
真正难的不是选 pivot，而是意识到：单靠换策略不能根治退化问题。工业级实现（如 Go 的 sort 包）会在递归深度超阈值时自动切回堆排序——这点自己写快排时最容易忽略。
