应优先使用 Go 标准库 sort.Ints;若手写快排,须原地 partition、选末尾为 pivot、终止条件为 low >= high,否则易致空间爆炸、引用失效或 panic。

别手写 quickSort,除非你明确需要控制分区逻辑、处理非 []int 类型(比如 []rune),或正在刷算法题。Go 标准库的 sort.Ints 已经是高度优化的内省排序(introsort),平均和最坏情况都比纯快排更稳。
为什么原地 partition 比新建切片更关键
新手常照搬 Python 写法:每次选 pivot,再用 append 拼 left 和 right 切片。这会导致三个严重问题:
- 空间爆炸:每次递归分配新底层数组,最坏空间复杂度从
O(log n)暴涨到O(n²) - 引用失效:传入的原始切片不会被修改,排序结果“看不见”
- 逃逸频繁:小切片频繁堆分配,GC 压力大,性能反而下降
正确做法是只用两个游标 i 和 j 在原切片上交换元素,partition 函数必须返回 pivot 的最终索引位置,供后续递归调用使用。
partition 函数里 pivot 选末尾还是中间?
选 arr[high] 是最安全的默认选择,不是因为它最优,而是因为:
立即学习“go语言免费学习笔记(深入)”;
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器,提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象,支持命名依赖等
- 边界清晰:闭区间
[low, high]下,high下标天然可用,无需额外计算或越界判断 - 实现简单:swap 逻辑统一(如
arr[i], arr[high] = arr[high], arr[i]),不易漏改 - 避免 panic:若选
arr[(low+high)/2],在递归传入空区间(如low > high)时仍需提前检查,而选末尾可把越界防护放在调用方统一处理
随机选 pivot 或三数取中能缓解已排序数组的最坏 O(n²),但属于过早优化;真实业务中,sort.Ints 已内置这些策略。
递归终止条件必须是 low >= high
这是最容易写错的一处。错误写法包括:
if len(arr) :递归操作的是子区间,<code>len(arr)是原始切片长度,永远不满足-
if low == high:漏掉空区间(low > high)情况,某些 pivot 策略下会无限递归 -
if low >= len(arr):第一次就 panic,因low通常为 0
正确逻辑是:子区间含 0 个或 1 个元素时停止,即 low >= high —— 这覆盖了 low > high(空)和 low == high(单元素)两种基础情形。
真正难的不是写对一次 partition,而是确保所有递归调用都严格按闭区间传递 low 和 high,且每次 swap 都作用于原底层数组。稍有松懈,就会出现“看起来排好了,但原切片没变”或者“panic: runtime error: index out of range”。

















