排序算法面试要点
| 算法 | 时间 | 空间 | 稳定 | |------|------|------|------| | 快排 | O(n log n) 均 | O(log n) 栈 | 否 | | 归并 | O(n log n) | O(n) | 是 | | 堆排序 | O(n log n) | O(1) | 否 | | 计数/桶 | O(n+k) | O(k) | 视实现 |
快排 partition：选 pivot，双指针交换，递归左右。工程上 std::sort / sort.Slice 多为 introsort。
归并 适合链表排序、逆序对计数（merge 时统计）。
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)二分查找模板
在 有序数组 找 target：
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1左边界（第一个 ≥ x）：
def lower_bound(nums, x):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < x:
lo = mid + 1
else:
hi = mid
return lo统一用 lo < hi、hi = len 避免 off-by-one。
二分答案
单调性不在数组值，而在 可行性函数 can(mid)：
- 分割数组的最大最小和
- 吃香蕉速度 K
- 在 D 天内运货
def min_eating_speed(piles, h):
def enough(speed):
return sum((p + speed - 1) // speed for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if enough(mid):
hi = mid
else:
lo = mid + 1
return lo与 Week 1 联系
双指针依赖排序；哈希 + 排序处理三数之和。站内 /chapters/algorithm-lab/plan-56-days 含排序与二分专题。
面试 checklist
- 循环不变量：
[0, lo)不满足，[hi, n)不满足。 - 溢出：Go/Java 用
lo + (hi-lo)/2。 - 重复元素：找左/右边界模板。
练习
排序：手写快排 partition、链表归并。二分：搜索旋转数组、找峰值、答案二分 2 题。
实战巩固与面试表达
本篇属于 8 周冲刺 week03-sorting-binary-search 主题。复习时先闭卷回答 frontmatter 中三张 flashcard，再展开口述两个「为什么」：为什么这种方案能 work、边界失败时如何降级。与相邻章节对照：算法篇强调复杂度与模板，Go 篇强调工程默认写法，中间件篇强调线上故障案例。
动手与自检清单
用 25 分钟限时做 1 道相关练习题或画出一张架构/数据结构示意图；用 5 分钟写 STAR 片段说明你在项目里是否用过类似技术。记录 3 个面试追问及你的标准答法，存入 /zh/notebook/master-plan 笔记。若某点不熟，回到对应 /chapters 交互 Lab 重新走一遍流程，比死记卡片更有效。
易错点提醒
避免只背名词不会画图；避免只说优点不谈 trade-off（性能、一致性、运维成本至少提一项）；避免把学习 Demo 说成百万 QPS 生产。回答时使用「场景 → 方案 → 结果 → 反思」四段式，体现工程成熟度。
补充要点
旋转数组二分找 pivot；峰值元素；二分实数答案精度控制。快排最坏避免：随机 pivot。稳定性需求选归并。Java Arrays.sort 对象用 TimSort。