快排分区必须用双指针,因单循环无法同时控制左右边界收缩,易致漏交换、越界或pivot归位错误;Lomuto用i/j单向扫描更安全,Hoare需end先动以保证相遇点≤pivot。

为什么快排分区必须用双指针,而不是单循环遍历
因为分区(partition)的本质是把数组重排成「≤pivot|>pivot」两段,且要原地完成——不能新建切片,也不能破坏原始底层数组。单循环遍历无法同时控制左右边界收缩,容易漏掉交换、越界或 pivot 归位错误。
典型错误是写成 for j := 0; j 然后靠 if 判断塞进 left/right 切片,这直接违背“原地”要求,append 会分配新底层数组,原切片不变。
- 双指针(通常叫
i和j)一个负责标记「≤pivot 的右边界」,另一个负责扫描整个区间 -
i初始为low - 1,表示已确认 ≤pivot 的区域末尾;j从low开始向右推进 - 每次
arr[j] 时,i++并交换arr[i]和arr[j],确保i左侧永远合规 - 最后
arr[i+1]和arr[high](pivot)交换,pivot 就落在了正确位置
partition 函数里 len(arr) - 1 为什么是危险操作
空切片时 len(arr) 是 0,len(arr) - 1 就是 -1,直接当索引用会 panic: index out of range。更隐蔽的是递归传入子切片(如 arr[lo:hi])时,len(arr) 返回的是子切片长度,不是原始数组长度,但你真正需要的是 hi - 1 这个右边界下标。
- 永远不要在 partition 中写
pivot := arr[len(arr)-1],应显式接收high int参数,用arr[high] - 循环条件必须是
j ,不是j ,否则子递归会越界 - 判断
low >= high必须放在递归入口,不能只靠 for 循环自然退出
为什么 end 必须先走、start 后走(Lomuto vs Hoare 风格)
这是 pivot 归位安全性的关键。如果你选最左元素为 pivot,并让 start 先动,遇到多个相等值时,可能把 pivot 换到中间一个相等值上,导致最终归位位置左侧出现 >pivot 的数——分区失败。
标准 Lomuto 分区(Go 官方示例常用)用单边扫描 + i/j 双指针,规避了这个问题;而 Hoare 风格(左右对撞)则强制要求 end 先从右往左找第一个 start 从左往右找第一个 > pivot 的数。顺序颠倒,结果就不可控。
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器,提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象,支持命名依赖等
- Hoare 风格中,若
start先动,且遇到arr[start] == pivot,它不会停,继续右移,可能跳过本该交换的位置 -
end先动能保证:相遇点的值一定 ≤ pivot,所以和 pivot 交换后,左侧段严格满足 ≤ pivot - 实际工程中建议统一用 Lomuto(即
i/j单向扫描),逻辑更直白,边界更易控
sort.Slice 能替代手写快排吗?什么情况下必须自己写
能,而且绝大多数情况应该用 sort.Slice。它经过 Go 团队多年优化,防退化、处理 nil、支持任意类型、自动选择 pivot 策略(比如三数取中),还带内省机制避免 O(n²)。
手写快排只在三种场景必要:算法题强制要求、教学演示、或嵌入式环境禁用标准库。但只要动手写,就必须直面那些被 sort.Slice 封装掉的细节:
- 空切片或单元素切片必须提前 return,否则
high = len(arr)-1会得 -1 -
Less函数里字段为 nil 时,不加判空会 panic,而手写快排里类似逻辑全得自己写 - 递归深度无限制时可能栈溢出,
sort.Slice内部用了迭代+栈模拟来缓解
最常被忽略的一点:手写版本返回的是新切片(如用 append 拼接),而 sort.Slice 是原地修改。如果你写了 return append(...),调用方看到的只是副本,原变量没变——这点在调试时极难察觉。
golang免费学习笔记(深入):立即使用
在学习笔记中,你将探索golang的核心概念和高级技巧!










