排序、二分、DFS/BFS等基础算法的原理与要点
答案要点
- 快排平均 O(n log n)、最坏 O(n²)、不稳定;归并稳定 O(n log n) 需 O(n) 空间
- 二分要求有序,O(log n),区间定义要前后一致
- mid 用 l+(r−l)/2 防止整数溢出
- DFS 用递归或栈,适合回溯、连通性;BFS 用队列,适合无权图最短路
- 图遍历需要 visited 标记避免重复访问
易错点
- 二分区间开闭定义和循环条件、更新方式不一致,导致死循环或漏解
- 以为快排一定是 O(n log n),忽略最坏情况
- BFS 在出队时才标记 visited,导致同一节点重复入队
面试官常见追问
- 快排最坏情况怎么出现、怎么避免?
- DFS 递归太深怎么办?
- 二分找第一个大于等于 target 的位置怎么写?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。