排序与查找¶
学习目标¶
学完本章后，学习者应该能够：
- 理解常见排序算法的复杂度和适用场景。
- 掌握二分查找的前提和边界。
- 理解 Top K 问题的常见解法。
- 能正确使用 Go 的
sort包。
为什么要学排序与查找¶
排序和查找是很多后端功能的基础：
- 列表排序。
- 排行榜。
- 分页。
- 去重。
- Top N。
- 时间线。
- 数据归并。
- 批处理结果合并。
很多系统慢，不是因为业务复杂，而是因为用了错误的查找方式或重复排序。
常见排序算法¶
| 算法 | 平均时间 | 额外空间 | 特点 |
|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 教学用，工程少用 |
| 插入排序 | O(n²) | O(1) | 小数组或基本有序时表现不错 |
| 快速排序 | O(n log n) | O(log n) | 平均快，最坏可退化 |
| 归并排序 | O(n log n) | O(n) | 稳定，适合链表和外部排序思想 |
| 堆排序 | O(n log n) | O(1) | 可原地排序，不稳定 |
工程中通常不手写排序，优先使用标准库。
Go sort 包¶
排序整数：
排序结构体：
type User struct {
Name string
Age int
}
users := []User{
{Name: "alice", Age: 30},
{Name: "bob", Age: 20},
}
sort.Slice(users, func(i, j int) bool {
return users[i].Age < users[j].Age
})
注意：排序会修改原 slice。如果调用方还需要原顺序，应先复制。
二分查找¶
二分查找的前提是数据已经有序。
func BinarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
复杂度是 O(log n)。
常见错误：
- 数据没有排序就二分。
- 边界条件写错。
mid := (left + right) / 2在某些语言里可能溢出。- 不清楚要找等于、大于等于，还是最后一个小于等于。
Top K¶
Top K 问题是找出最大或最小的 K 个元素。
常见解法：
- 全量排序：O(n log n)，简单但可能浪费。
- 小顶堆维护 K 个最大元素：O(n log k)。
- 快速选择：平均 O(n)，实现更复杂。
如果只是找前 10 个最大值，对 100 万条数据全量排序通常不是最优。
Go 后端实际应用例子¶
例子一：按创建时间排序返回接口列表¶
type Article struct {
ID int64
Title string
CreatedAt time.Time
}
func SortArticlesByCreatedAtDesc(articles []Article) {
sort.Slice(articles, func(i, j int) bool {
return articles[i].CreatedAt.After(articles[j].CreatedAt)
})
}
如果数据来自数据库，优先考虑让数据库通过索引排序和分页，而不是把大量数据拉到应用内排序。
例子二：在有序配置中查找命中的灰度阈值¶
假设灰度规则按阈值升序排列，可以用二分查找找到第一个大于等于用户 hash 的规则：
type Rule struct {
UpperBound int
Name string
}
func MatchRule(rules []Rule, value int) (Rule, bool) {
idx := sort.Search(len(rules), func(i int) bool {
return rules[i].UpperBound >= value
})
if idx == len(rules) {
return Rule{}, false
}
return rules[idx], true
}
二分查找在配置匹配、时间区间定位、版本区间查找里很常见。
排序与数据库¶
后端开发中，排序经常交给数据库：
但要注意：
- 排序字段是否有索引。
- 排序是否结合分页。
- 大 offset 分页是否会变慢。
- 是否需要稳定排序。
- 是否应该用游标分页。
算法意识会帮助你理解为什么某些 SQL 排序很慢。
常见误区¶
- 误区一：需要 Top K 就先全量排序。
如果只要 K 个元素，堆或快速选择可能更合适。
- 误区二：二分查找只要会模板就行。
工程中更常见的是边界二分，例如找第一个大于等于某值的位置。
- 误区三：排序只是内存里的事情。
数据库排序、搜索引擎排序、排行榜排序都和后端系统性能直接相关。
实战任务¶
给定一组用户访问量，找出访问量最高的前 10 个用户。
要求：
- 先用全量排序实现。
- 再用小顶堆思路描述优化方案。
- 对比两种方案复杂度。
- 思考如果数据来自数据库，是否应该在应用内排序。
参考答案
全量排序实现：
type UserVisit struct {
UserID int64
Count int
}
func TopUsersBySort(users []UserVisit, k int) []UserVisit {
if k > len(users) {
k = len(users)
}
cp := append([]UserVisit(nil), users...)
sort.Slice(cp, func(i, j int) bool {
return cp[i].Count > cp[j].Count
})
return cp[:k]
}
复杂度是 O(n log n)，实现简单。
小顶堆思路：维护一个大小为 k 的小顶堆。遍历所有用户访问量，如果堆未满就加入；如果当前访问量大于堆顶，就替换堆顶。最终堆中就是 Top K。复杂度是 O(n log k)，适合 k 远小于 n 的情况。
如果数据已经在数据库里，优先考虑：
但前提是要评估索引、数据量和查询成本。不要默认把全量数据拉到应用内排序。
面试题¶
1. 快速排序和归并排序有什么区别？¶
参考答案
快速排序平均时间复杂度 O(n log n)，通常原地排序，平均性能好，但最坏情况可能退化到 O(n²)，且不稳定。归并排序时间复杂度稳定为 O(n log n)，是稳定排序，但通常需要 O(n) 额外空间。
工程中不一定手写，但要理解它们的复杂度、稳定性和空间成本。
2. 二分查找的前提是什么？¶
参考答案
二分查找的前提是数据有序，并且可以高效访问中间位置。数组或 slice 适合二分，链表不适合，因为访问中间节点不是 O(1)。
另外要明确查找目标：是找等于目标的元素，还是找第一个大于等于、最后一个小于等于的位置。不同目标边界写法不同。
3. Top K 有哪些常见解法？¶
参考答案
常见解法有全量排序、小顶堆和快速选择。全量排序简单，复杂度 O(n log n)；小顶堆维护 K 个元素，复杂度 O(n log k)，适合 K 远小于 n；快速选择平均 O(n)，但实现和边界更复杂。
工程中如果数据在数据库里，还要考虑能否用索引和 SQL 排序直接得到结果，避免把大量数据拉到应用内。
4. 为什么大 offset 分页可能很慢？¶
参考答案
大 offset 分页通常需要数据库先扫描或排序大量记录，然后丢弃前面的 offset 条，只返回后面的 limit 条。offset 越大，浪费越多。
常见优化是游标分页，例如基于 created_at 或自增 ID 记录上一次位置，用 WHERE id < last_id ORDER BY id DESC LIMIT 20 这类方式减少扫描。
5. Go 的 sort.Slice 使用时要注意什么？¶
参考答案
sort.Slice 会原地修改 slice 顺序。如果调用方还需要原顺序，应先复制一份。比较函数必须满足严格弱序，否则排序结果可能不稳定或不符合预期。
如果需要稳定排序，可以使用 sort.SliceStable，但稳定排序可能有额外成本。