02.5.2 排序算法与设计
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序
这个知识域解决什么问题
排序是组织有序数据的基础。本知识域围绕 基础排序与稳定性 → 快排与三路划分 → 归并排序与逆序对 → 堆排序与工程排序 展开;不仅要会手写算法,还要能从稳定性、空间、最坏复杂度与数据特征角度选型。
知识地图
基础排序与稳定性(1)
→ 快排与三路划分(2)
→ 归并排序与逆序对(3)
→ 堆排序与工程排序(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.5.2.1 | 基础排序与稳定性 | 冒泡/选择/插入、稳定性判定、复杂度对比、原地与非原地、比较下界、计数/桶/基数概念 | 20 |
| 02.5.2.2 | 快排与三路划分 | Lomuto/Hoare 划分、pivot 策略、退化优化、三路划分、荷兰国旗、快速选择、递归栈控制 | 20 |
| 02.5.2.3 | 归并排序与逆序对 | 分治合并、稳定归并、链表归并、逆序对批量计数、右侧更小元素、自底向上、BIT 预告 | 20 |
| 02.5.2.4 | 堆排序与工程排序 | 堆排实现、Top-K 堆、双堆中位数、外部排序多路归并、工程混合排序、选型总结 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。
学习路径
先 1 掌握基础排序性质与稳定性对比,2 写熟快排划分与三路划分、快速选择,3 理解归并合并与逆序对计数,最后 4 掌握堆排、Top-K 与外部排序工程选型。
自检
- [ ] 能列全稳定/不稳定排序清单并解释原因
- [ ] 能手写 Lomuto/Hoare 划分与三路划分,说明最坏退化与优化
- [ ] 能写归并排序并用合并过程批量统计逆序对
- [ ] 能解释建堆 O(n),写堆排与 Top-K 堆方向选择
- [ ] 能说明外部排序流程与 I/O 轮次口径
- [ ] 能按稳定性、空间、最坏复杂度与数据特征给出排序选型