首页/数据结构/07-sorting/内部排序算法对比 🔗 在 Obsidian 中打开
数据结构 · 07-sorting

内部排序算法对比

难度 ★★★重要度 ★★ 考查频率 低题型 综合对比 数据结构/排序排序算法稳定性
速查
内部排序指全部数据在内存中完成的排序。408 要求掌握：插入（直接/折半/希尔）、交换（冒泡/快排）、选择（简单选择/堆）、归并、基数。比较类排序下界 $O(n\log n)$；不稳定口诀"快选希堆"。

速查 ▾

项目值
主题内部排序算法对比
核心概念全部记录存于内存的排序；408 考查约 8 种排序算法
时间复杂度最好 $O(n)$（插入/冒泡）；平均 $O(n\log n)$（快排/堆/归并）；最坏 $O(n^2)$（插入/选择/快排）；基数 $O(d(n+r))$
稳定性部分稳定、部分不稳定（口诀：快选希堆）
难度⭐⭐⭐

核心概念 ▾

内部排序是指待排序记录全部存放在内存中进行的排序过程。408 大纲要求掌握以下排序算法：

  • 插入排序：直接插入排序、折半插入排序、希尔排序
  • 交换排序：冒泡排序、快速排序
  • 选择排序：简单选择排序、堆排序
  • 归并排序：二路归并排序
  • 基数排序：按位分配收集

稳定性：若排序后相等元素的相对顺序不变，则称该排序算法稳定。

比较类排序的下界：基于比较的排序算法，最坏情况下时间复杂度下界为 $O(n\log n)$。

关键定义 ▾

概念定义
稳定排序排序后相等元素保持原有相对顺序
内排序所有数据在内存中完成排序
外排序数据量大，需要在内外存之间交换数据
趟排序过程中对数据进行的一次完整扫描或处理
堆完全二叉树，大根堆：父 $\geq$ 子；小根堆：父 $\leq$ 子
枢轴(pivot)快速排序中选定的划分基准元素

重点考法 ▾

考点说明
时间/空间复杂度最好、最坏、平均情况，需分别记忆
稳定性判断快速、希尔、简单选择、堆排序不稳定
快排的划分过程选定 pivot，左右指针交替扫描，写出每趟结果
堆的调整（筛选）插入元素上浮，删除堆顶下沉，写出调整过程
给定序列判断排序方法根据中间状态推断使用了哪种排序
各排序的适用场景数据量小用插入，大规模用快排/归并，需稳定用归并

易错点 ▾

  • 不稳定的排序：快速排序、希尔排序、简单选择排序、堆排序（口诀：快选希堆）
  • 快速排序平均性能最好 $O(n\log n)$，但最坏为 $O(n^2)$（已有序时退化）
  • 堆排序最坏时间复杂度仍为 $O(n\log n)$，但常数因子较大
  • 归并排序空间复杂度为 $O(n)$，不是 $O(1)$
  • 基数排序不是基于比较的排序，时间复杂度为 $O(d(n+r))$，d 为位数，r 为基数
  • 折半插入排序仅减少比较次数（$O(n\log n)$），移动次数仍为 $O(n^2)$
  • 希尔排序的时间复杂度与增量序列有关，不稳定

核心结论 ▾

  1. 直接插入排序：最好 $O(n)$，最坏/平均 $O(n^2)$，稳定，空间 $O(1)$
  2. 冒泡排序：最好 $O(n)$，最坏/平均 $O(n^2)$，稳定，空间 $O(1)$
  3. 快速排序：平均 $O(n\log n)$，最坏 $O(n^2)$，不稳定，空间 $O(\log n)\sim O(n)$
  4. 简单选择排序：最好/最坏/平均均为 $O(n^2)$，不稳定，空间 $O(1)$
  5. 堆排序：最好/最坏/平均均为 $O(n\log n)$，不稳定，空间 $O(1)$
  6. 归并排序：最好/最坏/平均均为 $O(n\log n)$，稳定，空间 $O(n)$
  7. 基数排序：$O(d(n+r))$，稳定，空间 $O(n+r)$，非比较排序

记忆卡片 ▾

哪些排序是稳定的？
直接插入、折半插入、冒泡、归并、基数排序是稳定的；希尔、快排、简单选择、堆排序不稳定。
最好情况下为 $O(n)$ 的排序？
冒泡排序（已有序时只需一趟比较）和直接插入排序（已有序时无需移动）。
快排的最坏情况？
已有序时退化为 $O(n^2)$，可通过随机选枢轴或三数取中优化。
空间复杂度为 $O(n)$ 的排序？
归并排序需要 $O(n)$ 辅助空间；基数排序需要 $O(n+r)$ 空间。
堆排序的时间复杂度特点？
最好/最坏/平均均为 $O(n\log n)$，不稳定，空间 $O(1)$，适合大数据量。

交互动画 ▾

直接插入稳定 冒泡稳定 快速不稳定 简单选择不稳定 堆排序不稳定 归并稳定 希尔不稳定 基数稳定
8 种内部排序算法一览；点击「高亮不稳定」口诀验证
稳定：直接插入 / 折半插入 / 冒泡 / 归并 / 基数
宏观步 1 / 11　同一输入 5,3,8,1,6,2,7,4（8 个小木板）
未排 比较中 交换/移动 枢轴 当前插入 已就位
冒泡排序稳定 · O(n²) · 一趟无交换即提前结束比较 0 · 移动 0
插入排序稳定 · 平均 O(n²)，近有序时 O(n)比较 0 · 移动 0
快速排序不稳定 · 平均 O(n log n)，最坏 O(n²)比较 0 · 移动 0
堆排序不稳定 · 恒为 O(n log n)，空间 O(1)比较 0 · 移动 0
四种排序对同一数据并排推进：每一步同时高亮该步发生的所有比较与交换，实时统计比较/移动次数。可用「下一步」逐段查看，或「▶ 播放」自动演示。
复杂度小结：冒泡/插入平均 O(n²)（近有序时冒泡/插入可达 O(n)）；快速平均 O(n log n)、最坏 O(n²)；堆排序恒为 O(n log n) 且空间 O(1)。选型看数据规模与是否要求稳定。
怎么记不稳定只有 4 个，口诀"快选希堆"：快速、简单选择、希尔、堆排序。其余均稳定。

相关知识点

哈夫曼树与编码 外部排序