主题
第七章 查找、排序与选择问题
1. 为什么把查找、排序和选择放在一起
很多教材把排序单独成章，但如果从问题结构看，查找、排序、选择其实高度相关：
- 查找关心如何快速定位元素。
- 排序关心如何建立全局顺序。
- 选择关心如何只找出第
k小或第k大，而不必完成全部排序。
它们共同围绕“有序性如何被利用或建立”展开，因此放在一起更有助于形成整体视角。
2. 二分查找：有序数组的代表性操作
二分查找适用于有序数组或有序切片。它的思想不是从头扫描，而是每次比较中点，把搜索区间减半。
go
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) 结论就不成立。
3. 排序算法关注的四个维度
评价排序算法时，不应只看时间复杂度，还要同时看：
- 是否稳定。
- 是否原地。
- 最坏复杂度和平均复杂度。
- 是否适合数据分布特征。
例如：
- 归并排序稳定，但要额外空间。
- 快速排序平均很快，但最坏可能退化到
O(n^2)。 - 堆排序上界稳定在
O(n log n)，但缓存局部性不如快速排序。
4. 插入排序：局部有序逐步扩展
插入排序的思想是把序列分成“左边已排序”“右边未排序”两部分，每次从未排序区取一个元素，插入左边合适位置。
go
func InsertionSort(nums []int) {
for i := 1; i < len(nums); i++ {
key := nums[i]
j := i - 1
for j >= 0 && nums[j] > key {
nums[j+1] = nums[j]
j--
}
nums[j+1] = key
}
}虽然最坏复杂度是 O(n^2)，但在数据本来就接近有序、小规模排序、在线插入等场景下，它很有价值。
5. 归并排序：分治与稳定性的典型代表
归并排序把数组不断二分，分别排好左右两边，再进行合并。
go
func MergeSort(nums []int) []int {
if len(nums) <= 1 {
out := make([]int, len(nums))
copy(out, nums)
return out
}
mid := len(nums) / 2
left := MergeSort(nums[:mid])
right := MergeSort(nums[mid:])
return merge(left, right)
}
func merge(a, b []int) []int {
out := make([]int, 0, len(a)+len(b))
i, j := 0, 0
for i < len(a) && j < len(b) {
if a[i] <= b[j] {
out = append(out, a[i])
i++
} else {
out = append(out, b[j])
j++
}
}
out = append(out, a[i:]...)
out = append(out, b[j:]...)
return out
}归并排序最重要的教育意义在于：它清楚地展示了分治、递归树和稳定合并这几件事如何配合。
6. 快速排序：局部划分，整体逼近
快速排序的关键不是“快速”这个名字，而是划分（partition）思想：选择一个基准，把小于它的放左边，大于它的放右边，然后递归处理左右两侧。
go
func QuickSort(nums []int) {
var sort func(int, int)
sort = func(left, right int) {
if left >= right {
return
}
pivot := partition(nums, left, right)
sort(left, pivot-1)
sort(pivot+1, right)
}
sort(0, len(nums)-1)
}
func partition(nums []int, left, right int) int {
pivot := nums[right]
i := left
for j := left; j < right; j++ {
if nums[j] < pivot {
nums[i], nums[j] = nums[j], nums[i]
i++
}
}
nums[i], nums[right] = nums[right], nums[i]
return i
}快速排序的平均复杂度是 O(n log n)，但若基准选得极差，例如总是选到最值，就会退化到 O(n^2)。这也是为什么工程中通常会做随机化或三数取中等优化。
7. 堆排序：利用堆序结构完成排序
堆排序基于前一章的堆结构：
- 先建堆。
- 每次把堆顶最值换到数组末尾。
- 缩小堆范围并继续下沉。
它的优点是最坏时间复杂度稳定在 O(n log n)，额外空间小；缺点是常数和缓存局部性通常不如优秀实现的快速排序。
8. 稳定性为什么重要
若有一组记录，先按次关键字排，再按主关键字排，则第二次排序若稳定，次关键字的相对次序不会被打乱。这在多字段排序里非常常见。
例如电商订单可先按创建时间排，再按状态排；如果第二次算法稳定，相同状态下仍保留原先时间顺序。
9. 选择问题：不必全排，只找第 k 小
有时我们并不关心完整有序序列，只想找中位数、前 k 大、前 k 小。若为了这个目标仍然把整个数组完全排序，就可能做了多余工作。
Quickselect 就是典型做法。它沿用快速排序的划分思想，但只递归进入包含目标排名的一侧。
go
func QuickSelect(nums []int, k int) int {
left, right := 0, len(nums)-1
target := k
for left <= right {
pivot := partition(nums, left, right)
if pivot == target {
return nums[pivot]
}
if pivot < target {
left = pivot + 1
} else {
right = pivot - 1
}
}
return -1
}如果 k=0，找的是最小值；如果 k=len(nums)/2，找的是中位数位置元素。
10. 排序算法比较
| 算法 | 平均复杂度 | 最坏复杂度 | 稳定性 | 额外空间 |
|---|---|---|---|---|
| 插入排序 | O(n^2) | O(n^2) | 稳定 | O(1) |
| 归并排序 | O(n log n) | O(n log n) | 稳定 | O(n) |
| 快速排序 | O(n log n) | O(n^2) | 不稳定 | 递归栈 |
| 堆排序 | O(n log n) | O(n log n) | 不稳定 | O(1) |
不要把这张表当作最终答案。真正的选择还要结合：
- 数据规模。
- 是否要求稳定。
- 是否允许额外内存。
- 输入是否几乎有序。
11. 本章常见误区
- 认为排序算法只要背复杂度就够了。
- 忽视稳定性。
- 不理解二分查找依赖“有序前提”。
- 为找第
k小而盲目全排序。 - 只会写模板，不会解释划分、合并和堆序为什么成立。
12. 本章小结
这一章的主线是“如何建立或利用有序性”：
- 二分查找利用已有顺序。
- 排序算法建立全局顺序。
- 选择算法只建立足够的局部顺序。
学到这里，应当能够把数组、堆、递归、分治这些前面章节的知识重新串起来。最后一章会把整套课程拉回工程视角，做统一比较和实践建议。
13. 图解版补充
如果你想把“排序过程”看得更直观，而不是只停留在复杂度表和代码模板上，可以继续看：
这页额外补了冒泡、选择、插入、归并、快速、堆排序的分步骤解释，并给了几张可直接播放的动态示意图。
如果你想横向比较更完整的排序家族，再继续看：