罗罗编程学习记录
本页内容 展开查看

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 轮次口径
  • [ ] 能按稳定性、空间、最坏复杂度与数据特征给出排序选型