递归边界必须是 left >= right,partition 必须将 pivot 交换至最终位置并返回其下标 p,左右递归调用应为 quickSort(arr, left, p-1) 和 quickSort(arr, p+1, right),传下标比传切片更安全可控。

递归调用的边界必须是 left >= right,不是 len(arr)
手写快速排序时,最常误写的终止条件是 if len(arr) —— 这在递归中完全失效。因为每次传入的是子切片(如 <code>arr[lo:hi]),len(arr) 只反映当前切片长度,但递归函数签名若定义为 QuickSort(arr []int, left, right int),那所有逻辑都基于 left 和 right 下标区间操作。一旦用全局长度判断,left 和 right 可能早已越界或未覆盖实际待排段。
正确做法只依赖区间有效性:if left >= right 意味着子数组长度 ≤ 0(left > right)或仅含 1 个元素(left == right),此时无需再分。这个判断不依赖切片底层数组大小,也不受 append 或 copy 干扰。
partition 返回值必须是 pivot 的最终索引,否则递归会漏排或 panic
partition 函数不只是“把小的放左、大的放右”,它必须把 pivot 元素交换到其排序后应处的位置,并返回该位置下标——这个下标将直接用于左右递归的分界。常见错误包括:
- 忘记把 pivot 放回中间(比如只做
i++/j--循环,没执行最后的arr[i], arr[high] = arr[high], arr[i]) - 返回了
i但没确认i是否真的对应 pivot 归位后的索引(例如循环结束时i可能已越界) - 递归调用写成
QuickSort(arr, left, i)而非QuickSort(arr, left, i-1),导致 pivot 被重复参与下一轮排序
典型安全写法:partition 结束后,pivot 落在索引 p,则左右递归必须是 QuickSort(arr, left, p-1) 和 QuickSort(arr, p+1, right)。
立即学习“go语言免费学习笔记(深入)”;
递归参数传切片视图 vs 传下标:选后者更可控
两种主流写法:
① 传子切片:quicksort(arr[:p]) 和 quicksort(arr[p+1:])
② 传下标:quicksort(arr, left, p-1) 和 quicksort(arr, p+1, right)
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器,提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象,支持命名依赖等
前者看似简洁,但隐患明显:
-
arr[p+1:]在p == len(arr)-1时变成空切片arr[len(arr):],合法;但若p == len(arr)(因 bug 导致),就会 panic - 切片视图可能意外包含原数组未初始化部分(尤其当底层数组比切片长),
partition过程中读取脏值 - 调试时难以追踪原始下标范围,日志和断点容易失焦
传下标方式明确约束操作边界,所有访问都经 left/right 校验,配合 if left >= right 终止,逻辑闭环更紧。
为什么标准库不用手写递归快排?sort.Slice 已处理所有复杂点
真实项目里几乎不需要手写 QuickSort 函数。Go 标准库的 sort.Slice 内部使用了混合策略:小数组用插入排序,中等规模用快排,大数组或检测到退化时自动切换为堆排序或归并排序。它还内置随机 pivot、三数取中、尾递归优化等机制。
你只需提供比较逻辑:sort.Slice(data, func(i, j int) bool { return data[i] 。自己实现时最容易忽略的,其实是退化场景防御——比如对已排序数组反复选末尾为 pivot,会退化成 O(n²);而标准库在递归深度超阈值时会主动降级算法。
手写唯一合理场景是教学、算法题或嵌入式受限环境。此时务必守住三点:原地交换、下标区间控制、pivot 归位验证——其余都是干扰项。

















