快速排序最坏时间复杂度为O(n²)，因每次pivot选为最值导致递归深度O(n)且每层扫描O(n)；Go标准库通过限制递归深度并自动切换至堆排序来保障O(n log n)最坏性能。
为什么快速排序会退化到 O(n²)
最坏情况发生在每次选的 pivot 都是当前子数组的最小或最大值，比如对已升序数组始终选最后一个元素作 pivot，会导致每次只减少一个元素，递归深度变成 O(n)，每层扫描仍是 O(n)，总时间就涨到 O(n²)。
Go 标准库怎么绕过这个坑
Go 的 sort.Sort 和 sort.Slice 并不是纯快排——它在递归深度超过 maxDepth(n) 时自动切到堆排序。这个阈值是 2 * ceil(log₂(n+1))，本质是限制栈深不超过完全二叉树深度的两倍。一旦触发，后续排序改用 heapSort，保证最坏也是 O(n log n)。
-
maxDepth不是拍脑袋定的：太浅会过早切堆排，影响平均性能；太深又起不到兜底作用 - 你写的自定义快排如果没有这层保护，就真的可能被恶意输入打穿
- 标准库没公开这个切换逻辑，但源码里
quickSort(data, 0, n, maxDepth(n))的第三个参数就是深度上限
自己实现时怎么防退化
不建议从零手写带防御的工业级快排，但若必须自研，三个低成本手段比随机选 pivot 更实在：
Golang Uber Dig
下载
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等
- 用三数取中（
arr[left]、arr[mid]、arr[right]的中位数）代替固定选首/尾，对部分有序数据效果立竿见影 - 当子数组长度 ≤ 12 时直接切到插入排序——小数组上快排常不如插排，且避免深度增加
- 检测是否连续多次选到极值（比如连续 3 次
pivot索引等于left或right），就强制改用随机索引
什么时候真该换算法
如果你的场景明确知道数据高度有序（如日志按时间追加后需重排）、或有确定的攻击面（比如用户可构造输入），别硬扛快排优化。直接用 sort.Slice 就行——它背后已经集成上述所有防护，且对 []int、[]string 等常见类型还有汇编优化路径。
真正容易被忽略的是：自定义 sort.Slice 比较函数里如果包含耗时操作（比如解析 JSON 字段再比大小），性能瓶颈根本不在排序算法本身，而在你的比较逻辑。先 profile，再决定要不要动底层。
golang免费学习笔记（深入）：立即使用
在学习笔记中，你将探索golang的核心概念和高级技巧！
