入门：三种 O(n²) 排序的定位、特性与稳定性
基于通用算法概念 · 核于 2026-07
速查
- 三种 O(n²) 排序的定位：冒泡、选择、插入都是比较型原地排序，平均/最坏 O(n²)、空间 O(1)、原地（in-place）——是学习排序的入门必修，也是工程里小数据量场景的实际选择。
- 每轮做什么：冒泡——相邻比较交换，大值逐轮「上浮」到末尾；选择——每轮在剩余区找最小放到前段；插入——把当前元素插进已排序的合适位置。
- 比较 vs 交换：比较次数（O(n²) 量级）决定「看了几次」，交换次数决定「搬了几次」——冒泡交换最多（O(n²)）、选择交换最少（O(n)）、插入介于两者之间（但搬移是连续的，缓存友好）。
- 最好情况：冒泡/插入在已有序或近乎有序时最好 O(n)（加优化的冒泡或插入只扫一遍）；选择无论数据是否有序都是 O(n²)（必须比完才能确定最小）。
- 稳定性：冒泡稳定（相等不交换）、插入稳定（相等不停下，插到右侧）、选择不稳定（跨距离交换会打乱相等元素的相对顺序）。
- 稳定性正式定义：排序后，值相等的元素仍保持原来的相对顺序，则称该排序稳定——「稳定」是待排序记录含多个相同 key 时才有意义的属性。
- 为什么还要学 O(n²)：①是理解排序（比较/交换/稳定性/原地）的基础；②大数据先排序时小数组兜底用插入排序（常数最小）；③面试常考稳定性判定与「为什么选择排序不稳定」。
- 插入排序的工程价值：n 小（典型 ≤32~64）或近乎有序时比快排/归并还快——Java
Arrays.sort基本类型、PythonTimsort、V8Array.sort在小数据段都退化为插入排序。 - 何时用插入排序：n ≤ 几十、或数据近乎有序、或「来一个排一个」的在线场景；逆序大数据则别用（退化为 O(n²)）。
- 进阶顺序：三种算法详解与对比 → 优化与稳定性分析 → 参考。
- 一句话：三种 O(n²) 里，冒泡最易、选择交换最少但不稳、插入工程价值最高——记住这一定位。
- 后续升级：把 O(n²) 优化到 O(n log n) 的是快排/归并/堆排，而混合排序（Timsort、pdqsort）在大数组用 O(n log n)、小数组切回插入排序，兼顾两者。
一、三种 O(n²) 排序的定位
排序算法按平均复杂度大致分两档：O(n²) 的简单排序（冒泡、选择、插入）与 O(n log n) 的高效排序（快排、归并、堆排）。本叶讲的三个都属前者，它们实现极简、常数小、空间 O(1)，是学习排序的入门必修。
为什么有了 O(n log n) 还要学 O(n²)？三个理由：
- 是理解排序的基础：比较、交换、稳定性、原地这些概念在 O(n²) 排序里最纯粹、最好理解；不学它们，快排为什么不稳定、归并为什么稳定都讲不清。
- 小数据量兜底：O(n log n) 排序有递归/分治的常数开销，n 很小时反而比插入排序慢——所以所有工业级排序在小数据段都退化为插入排序（详见后文工程价值）。
- 面试常考：稳定性判定、选择排序为什么不稳定、插入排序最好 O(n) 的条件，都是高频考点。
三者看似等价（都是 O(n²)），实则分工不同。理解它们的关键是抓住两个概念。
二、比较次数与交换次数
O(n²) 描述的是「比较 + 交换/搬移」的整体量级，但比较和交换是两回事：
- 比较次数：决定「看了几次元素之间的大小关系」，主要影响 CPU 比较开销。
- 交换/搬移次数：决定「实际移动了几次元素」，主要影响写内存开销（元素越大，交换越贵）。
三者在这两个量上的表现差异很大：
| 排序 | 比较次数（最坏） | 交换/搬移次数（最坏） | 备注 |
|---|---|---|---|
| 冒泡 | O(n²) | O(n²)（最多） | 每次只交换相邻，搬移代价高 |
| 选择 | O(n²)（固定，与有序无关） | O(n)（最少） | 每轮至多交换一次 |
| 插入 | O(n²) | O(n²) | 但搬移是连续的，缓存友好 |
选型的直觉：元素很大、交换昂贵 → 选择（交换最少）；元素小、近乎有序 → 插入（搬移连续、最好 O(n)）；教学/稳定性 → 冒泡。注意「交换最少」不代表「最快」——选择固定 O(n²) 比较，无法利用初始有序性，平均仍不快。
三、稳定性：排序的另一维度
稳定性（stability） 是排序算法除复杂度外的第二核心属性，正式定义是：
排序后，值相等的元素仍保持它们在原序列中的相对顺序，则该排序稳定；否则不稳定。
举例：原序列 [5a, 3, 5b, 2]（5a、5b 都等于 5，下标区分先后），稳定排序后 [2, 3, 5a, 5b]（5a 仍在 5b 前），不稳定排序可能得到 [2, 3, 5b, 5a]。
三者的稳定性结论（推导详见优化与稳定性分析）：
| 排序 | 稳定？ | 原因 |
|---|---|---|
| 冒泡 | 稳定 ✅ | 相邻比较，相等时不交换（> 而非 >=） |
| 插入 | 稳定 ✅ | 插入时遇到相等就停下，新元素插到右侧 |
| 选择 | 不稳定 ❌ | 跨距离交换，把后面的小值换到前面，可能越过相等元素 |
稳定性什么时候有用：当待排序记录有多个 key（如先按部门排，再按工龄排，希望同部门内工龄序不被破坏）时，必须用稳定排序做第二次排序——这是「稳定」真正的工程价值。快排不稳、归并稳、堆不稳，这也是它们选型的考量之一。
四、关键差异：能否利用初始有序性
三者对「输入是否已部分有序」的敏感度不同，这是选型的核心：
- 插入/冒泡：敏感。已有序时，插入每轮只比较一次就定位、冒泡（加优化）一轮无交换即终止——两者最好都是 O(n)。所以「近乎有序」的数组用插入排序极快。
- 选择：不敏感。每轮都必须把剩余元素全比一遍才能确定最小，与数据是否有序无关——无论输入多有序，都是 O(n²)。
这条差异解释了为什么插入排序是工程兜底、选择排序不是：插入能「沾有序的光」，选择不能。
五、为什么 O(n²) 仍有工程价值
工业级排序（Java Arrays.sort、Python list.sort、V8 Array.sort）都不是单一算法，而是混合排序：
- 大数据段用 O(n log n)：快排（pdqsort）或归并（Timsort）。
- 小数据段（典型
n ≤ 32~64）切回插入排序——因为 n 小时，O(n log n) 的递归/分治常数开销超过 O(n²) 的简单扫描，插入排序反而更快。
所以「插入排序」并非过时，它活在所有现代排序的「小数组分支」里。理解这一点，就理解了「为什么学了 O(n log n) 还要学 O(n²)」。
下一步
掌握了三种 O(n²) 排序的定位与两个核心概念（比较 vs 交换、稳定性）后，下一步逐一拆解三种算法的代码实现与复杂度对比表，见三种算法详解与对比。