分区操作必须单独封装,因其需严格保证:所有小于pivot的元素在左、大于的在右,且pivot最终落于排序后正确下标;混入递归函数易致越界、漏排或死循环,故须由partition返回pivot索引以安全划分区间。

分区操作为什么必须用 partition 单独封装
因为分区不是“找一个中间值然后 swap 两次”这么简单——它要保证:所有 arr[i] 的元素严格落在左半段,所有 arr[j] > pivot 的元素严格落在右半段,且 pivot 最终停在它排序后该在的下标位置。如果把这个逻辑混在递归函数里,边界错一位、i 或 j 多走一步,整个数组就可能漏排、越界或死循环。
常见错误现象:panic: runtime error: index out of range,或排序后部分数据逆序、重复元素位置错乱。
-
partition必须返回pivot的最终索引,供上层递归调用划分左右区间 - 不能直接对
arr[:pivot]和arr[pivot+1:]递归(这是切片版的简化写法,但隐藏了索引偏移风险) - 若用 Lomuto 方案(以
arr[high]为 pivot),i要从low - 1开始,否则第一个小于 pivot 的元素会被跳过
partition 里 i 和 j 的移动顺序为什么不能反
以 Hoare 分区方案为例(常用在双指针向中间收缩的实现中):先让 j 从右往左找第一个 的数,再让 i 从左往右找第一个 >= pivot 的数,然后交换。顺序反了会导致 i 和 j 在未相遇前就交叉,或者某侧元素没被充分扫描。
典型表现:小数组如 []int{3, 1, 2} 排序后变成 [2, 1, 3],中间值没归位。
- 必须是 “
j先动 → 判断 →i再动 → 判断 → 交换”,形成闭环控制 - 每次
i++或j--后都要立刻检查是否越界(i ),否则交换时下标非法 - 当
i == j时,这一轮分区结束,arr[i]就是 pivot 归位后的位置
选 pivot 用 arr[low]、arr[high] 还是 arr[(low+high)/2]
三种选法都合法,但行为差异明显:arr[low] 和 arr[high] 在已排序或近乎有序数组上极易触发最坏时间复杂度 O(n²);而中位数近似值(如 arr[(low+high)/2])能显著降低退化概率。
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器,提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象,支持命名依赖等
不过 Go 标准库 sort 实际采用的是三数取中(median-of-three)+ 随机回退策略,普通手写不必过度优化,但至少别固定用首/尾。
- 用
arr[high]最简洁,适合教学和小数据量验证 - 用
arr[(low+high)/2]对随机数据更鲁棒,且避免整数溢出(low+high可能超int)可改用low + (high-low)/2 - 生产代码建议加一层随机:用
rand.Intn(high - low + 1) + low选下标,再 swap 到末尾,再进 partition
原地排序时切片截取 arr[low:high+1] 的陷阱
Go 切片传递的是底层数组引用,看似方便,但递归中若直接传 arr[low:pivot] 和 arr[pivot+1:high+1],会丢失原始切片的容量信息,且 pivot 是相对当前子数组的偏移,不是全局下标——这会让调试时打印的 len(arr) 和你脑内预期不一致,尤其在嵌套多层后。
最容易被忽略的一点:分区函数返回的 pivotIndex 是相对于入参切片的起始下标(即 low),不是相对于原始数组。如果你在递归调用时误写成 QuickSort(arr, 0, pivotIndex-1),就全乱了。
- 始终用绝对下标传参:
QuickSort(arr, low, pivotIndex-1)和QuickSort(arr, pivotIndex+1, high) - 避免在
partition内部修改原始切片长度(如arr = arr[:n]),这会破坏上层对底层数组的视图 - 测试时用固定小数组(如
[]int{5,2,4,7,1})并单步打印每轮的low、high、pivotIndex,比看最终结果更能暴露索引偏差
golang免费学习笔记(深入):立即使用
在学习笔记中,你将探索golang的核心概念和高级技巧!










