Go 语言如何实现快速排序和二分查找？

Golang小白一枚，正在不断学习积累知识，现将学习到的知识记录一下，也是将我的所得分享给大家！而今天这篇文章《Go 语言如何实现快速排序和二分查找？》带大家来了解一下##content_title##，希望对大家的知识积累有所帮助，从而弥补自己的不足，助力实战开发！

靠谱的 quickSort 需随机选 pivot、双指针原地分区、小数组切片优化；快排+二分仅在一次排序多次查询时划算，单次查询用线性扫描更优。

Go 语言里怎么写一个靠谱的 quickSort？ Go 没有内置快速排序的通用函数（sort.Slice 底层虽用快排，但不暴露分区逻辑），自己实现时关键在三点：选基准、原地分区、避免最坏 O(n²)。别直接拿第一个元素当 pivot——小切片或已排序数据下极易退化。

实操建议：

• 用 rand.Intn(len(a)) 随机选 pivot 索引，再和末尾交换，比固定选首/尾更稳
• 分区用「双指针」：左指针找 ≥ pivot 的，右指针找 ≤ pivot 的，交换后收敛到分界点
• 递归前检查子数组长度，len(a) 时改用插入排序，减少小数组递归开销
• 别传切片副本，用 func quickSort(a []int, lo, hi int) 原地操作，避免内存分配

常见错误：递归调用时传错边界，比如写成 quickSort(a, lo, p-1) 却忘了 p 是 pivot 最终位置，实际应为 quickSort(a, lo, p-1) 和 quickSort(a, p+1, hi) —— 这里 p 必须被排除在外。

用 sort.SearchInts 做二分查找前要注意什么？ sort.SearchInts 要求输入切片必须升序，否则结果无意义。它返回的是「插入位置」，不是布尔值——哪怕目标不存在，也总会返回一个索引，得手动判断是否越界或值匹配。

实操建议：

• 先确认数据有序：sort.IsSorted(sort.IntSlice(data)) 可用于调试，但生产环境别跑这个（O(n)）
• 查存在性时，必须额外判断：idx
• 如果要找重复元素的左边界，不能直接用 SearchInts，得用 sort.Search 自定义条件：sort.Search(len(data), func(i int) bool { return data[i] >= target })
• 注意泛型替代方案：Go 1.21+ 可用 slices.BinarySearch（在 slices 包），行为一致但支持任意可比较类型

典型坑：把 sort.SearchInts 当作 contains 用，忽略返回值需校验，导致越界 panic 或逻辑错误。

快排 + 二分组合使用时性能陷阱在哪？ 快排后立刻二分看似合理，但若只查一次，排序成本（O(n log n)）远高于线性扫描（O(n)）。只有在「一次排序、多次查询」场景下才划算。

实操建议：

• 如果查询次数 k ，直接遍历更省事；超过才值得预排序
• 别在每次查询前重新排序——把排序结果缓存为包级变量或结构体字段
• 并发环境下，多个 goroutine 同时读已排序切片是安全的，但写（重排序）需加锁或用 sync.Once
• 内存敏感场景注意：快排原地但递归深度可能达 O(n)，极端情况栈溢出；可用尾递归优化或切换到迭代版分区

容易被忽略的是：Go 的 sort.Ints 已高度优化（内省排序，混合快排/堆排/插入），除非你明确知道数据分布特征，否则自研快排大概率更慢、更易出错。

好了，本文到此结束，带大家了解了《Go 语言如何实现快速排序和二分查找？》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多Golang知识！