第 14 章 · 经典排序、sort.Slice 与 Top N
本章目标：手写 冒泡、快速、归并 排序并理解复杂度；使用 sort.Slice / sort.SliceStable；实现 toolkit-go 慢请求 Top N 与 商品价格排序；对照 java-dev ch17 算法章；为 ch15 毕业项目 准备 internal/sortalgo 包。
学时建议：4～5 小时（含 2.5 小时跟练）
前置：完成 go-dev ch13（testing 与 benchmark）。
14.1 场景说明：Top N 慢请求
运营日报只需展示 耗时最高的 N 条 path（如 N=10）。access 日志经 ch11 聚合后得到 []SlowRow；需按 avg_ms 或 max_ms 降序 取 Top N。
internal/sortalgo/
├── bubble.go # 教学：O(n²)
├── quick.go # 分治：平均 O(n log n)
├── merge.go # 稳定：O(n log n)
├── topn.go # 工程：sort.Slice + TopN
└── sort_test.go # 表驱动 + benchmark| 需求 | 排序键 | 稳定？ |
|---|---|---|
| 慢请求 Top N | MaxMs 或 AvgMs 降序 | 否 |
| 商品目录 | Price（分）升序 | 同价按 Slug |
| 已发布优先 | IsPublished 降序，再 Price | 是 → SliceStable |
原则：工程 99% 用 sort 标准库；手写算法为理解复杂度与面试；数据量极大时用 heap Top K（选修）。
14.2 评价指标
| 指标 | 含义 |
|---|---|
| 时间复杂度 | 随 n 增长的操作次数（平均/最坏） |
| 空间复杂度 | 额外内存 |
| 稳定性 | 相等 key 排序后相对顺序是否不变 |
| 符号 | 直觉 |
|---|---|
| O(n²) | 双重循环朴素排序 |
| O(n log n) | 优秀比较排序下界 |
| O(1) | 原地、无额外数组 |
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) | ✅ |
| 快速 | O(n log n) | O(n²) | O(log n) | ❌ |
| 归并 | O(n log n) | O(n log n) | O(n) | ✅ |
| sort.Slice | O(n log n) | O(n log n) | O(log n) | ❌ |
| sort.SliceStable | O(n log n) | O(n log n) | O(n) | ✅ |
14.3 冒泡排序（教学）
// internal/sortalgo/bubble.go
package sortalgo
func BubbleSortInt(nums []int) {
n := len(nums)
for i := 0; i < n-1; i++ {
swapped := false
for j := 0; j < n-1-i; j++ {
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
swapped = true
}
}
if !swapped {
return // 已有序，提前结束
}
}
}相邻比较，较大元素「冒泡」到末尾；已有序时 O(n)。
14.4 快速排序
// internal/sortalgo/quick.go
package sortalgo
func QuickSortInt(a []int) {
if len(a) < 2 {
return
}
quickSortRange(a, 0, len(a)-1)
}
func quickSortRange(a []int, lo, hi int) {
if lo >= hi {
return
}
p := partition(a, lo, hi)
quickSortRange(a, lo, p-1)
quickSortRange(a, p+1, hi)
}
func partition(a []int, lo, hi int) int {
pivot := a[hi]
i := lo
for j := lo; j < hi; j++ {
if a[j] < pivot {
a[i], a[j] = a[j], a[i]
i++
}
}
a[i], a[hi] = a[hi], a[i]
return i
}最坏 O(n²)：已有序 + 固定 pivot；工程可用 随机 pivot 或直接用 sort.Ints。
mid 溢出（Java 对照）：Go 的 lo + (hi-lo)/2 安全，避免 (lo+hi)/2 溢出（C/Java 老坑）。
14.5 归并排序
// internal/sortalgo/merge.go
package sortalgo
func MergeSortInt(a []int) []int {
if len(a) <= 1 {
return a
}
mid := len(a) / 2
left := MergeSortInt(a[:mid])
right := MergeSortInt(a[mid:])
return mergeInt(left, right)
}
func mergeInt(left, right []int) []int {
out := make([]int, 0, len(left)+len(right))
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] <= right[j] {
out = append(out, left[i])
i++
} else {
out = append(out, right[j])
j++
}
}
out = append(out, left[i:]...)
out = append(out, right[j:]...)
return out
}稳定；适合 链表、外部大文件；空间 O(n)。
14.6 sort.Slice 与 SlowRow
// internal/sortalgo/topn.go
package sortalgo
import (
"sort"
"example.com/toolkit-go/internal/model"
"example.com/toolkit-go/internal/report"
)
func SortSlowRowsDesc(rows []report.SlowRow) {
sort.Slice(rows, func(i, j int) bool {
if rows[i].MaxMs != rows[j].MaxMs {
return rows[i].MaxMs > rows[j].MaxMs
}
return rows[i].Path < rows[j].Path // 次键字典序
})
}
func TopNSlowRows(rows []report.SlowRow, n int) []report.SlowRow {
if n <= 0 || len(rows) == 0 {
return nil
}
SortSlowRowsDesc(rows)
if n > len(rows) {
n = len(rows)
}
// 拷贝避免修改 caller 的 slice 语义混乱
out := make([]report.SlowRow, n)
copy(out, rows[:n])
return out
}
func SortProducts(products []model.Product) {
sort.SliceStable(products, func(i, j int) bool {
if products[i].Price != products[j].Price {
return products[i].Price < products[j].Price
}
return products[i].Slug < products[j].Slug
})
}model.Product（ch05/ch11 复习）：
type Product struct {
Slug string
Name string
Price int64 // 分
IsPublished bool
}14.7 Top N 与 heap（选修）
全排序 O(m log m)，m 为慢 path 数；若 m 很大而 N 很小，用 小顶堆 维护 Top N：