go 中靠谱快排需原地分区、随机 pivot、小数组切插入排序；二分查找推荐 sort.search 或统一左闭右开区间避免边界错误。
Go 语言里怎么写一个靠谱的快速排序
快速排序在 Go 中没有内置函数，得自己实现；但别直接抄教科书递归版本——容易栈溢出或性能差。关键点是：用原地分区、加随机 pivot 防最坏情况、小数组切到插入排序。
实操建议：
- 对
[]int这类基础类型，直接操作切片底层数组，避免传参拷贝 - 递归深度超过
log2(len)时强制切到堆排序（标准库sort.Sort就这么干），但日常小数据量可省略 - 分区函数推荐用 Lomuto 方式（易懂）或 Hoare 方式（交换少），别用单边扫描+额外空间
- 示例片段（Lomuto + 小数组优化）：
func quickSort(arr []int, low, high int) {
if high-low func partition(arr []int, low, high int) int {
randIndex := low + rand.Intn(high-low+1)
arr[randIndex], arr[high] = arr[high], arr[randIndex]
pivot := arr[high]
i := low - 1
for j := low; j <h3>为什么不用 <code>sort.Slice</code> 而要手写快排</h3><p><code>sort.Slice</code> 确实能一行排序，但它泛型开销大、不支持自定义分区逻辑，且无法和后续二分查找形成“同一份有序数据”的可控闭环。比如你要对结构体按某个字段排序后立刻查，又不想依赖 <code>sort.Search</code> 的闭包判断——这时候手写更稳。</p><p>常见错误现象：</p>
- 忘记对切片做
arr = append([]int(nil), arr...)深拷贝，导致原数据被意外修改 - 递归调用时传错边界，比如写成
quickSort(arr, low, p)导致无限递归 - 没设随机 pivot，遇到已排序数组退化成 O(n²)，本地测不出，压测才崩
Go 标准库的 sort.Search 怎么配合手写快排用
sort.Search 是通用二分查找入口，它不关心你怎么排的，只依赖你传入的闭包返回 bool。只要快排完数组是升序，它就能查。
使用场景：
- 查某个值是否存在：
idx := sort.Search(len(arr), func(i int) bool { return arr[i] >= target }) - 查第一个 ≥ target 的位置后，再判断
idx - 如果要查最后一个 ≤ target 的位置，闭包改成
return arr[i] > target，结果减一
注意：sort.Search 不校验数组是否真有序，乱序输入只会返回错误下标，不会 panic。
手写二分查找要注意的三个细节
自己写二分比调 sort.Search 更轻量，但边界极易出错。核心是统一用「左闭右开」区间，即 [left, right)，这样 while 条件恒为 left ，更新恒为 <code>right = mid 或 left = mid + 1。
容易踩的坑：
- 用
left + 「左闭右闭」时，<code>mid更新后漏掉+1或-1，导致死循环 - 计算
mid写成(left + right) / 2可能整数溢出，应改用left + (right-left)/2 - 查不到时返回什么？标准库返回长度，手写常返回
-1，但调用方必须显式判负，别直接当索引用
简单示例（左闭右开，查存在性）：
func binarySearch(arr []int, target int) int {
left, right := 0, len(arr)
for left <p>Go 的排序和查找组合起来并不难，难点在边界控制和一致性——快排输出必须严格升序，二分才能复用；一旦中间混了并发写或部分排序，结果就不可靠。实际项目里，除非有特殊需求（比如定制 pivot 策略或内存受限），否则优先用 <code>sort.Ints</code> + <code>sort.Search</code> 组合，更安全。</p>
