插入、选择、冒泡排序：三种 O(n²) 入门排序为何仍值得学
插入、选择、冒泡是三种最朴素的平方级排序，却是理解"算法设计"与"复杂度"的最佳起点。本文讲清它们的思想、代码、稳定性与适用场景，并说明为何现代语言仍把它们当作小数组的收尾算法。
本节你将能
学完这一节，你将能说清三件事：插入、选择、冒泡三种排序分别怎么排、它们的好/坏情况与稳定性有何差异、以及为什么看似"慢"的 O(n²) 排序今天仍无处不在。这是整个排序模块（B1–B7）的入口，后续归并、快排、堆排序都会回头比较它们。
一、为什么要先学"慢"的排序
很多人疑惑：既然有 O(n log n) 的快排、归并，为什么还要学 O(n²) 的入门三剑客？答案有两点。第一，它们思想极简、易于证明正确，是理解loop invariant（循环不变量）和复杂度分析的最佳练兵场；第二，它们的常数因子极小、且是原地排序，在对小数组或近乎有序的数据上，反而比复杂算法更快。现代标准库（如 C++ introsort、Python Timsort）都会在子数组足够小时切换回插入排序。
二、插入排序：像整理手牌一样
插入排序的核心类比是你打扑克：手里已排好序的牌，每摸到一张新牌，就从右往左找到它的位置插进去。算法对数组从第 2 个元素开始，把当前元素当作"key"，向左扫描并把比它大的元素逐个右移，最后空出的位置放上 key。
代码（Python）：
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
复杂度：最坏（逆序）与平均都是 O(n²)，但最好情况（已升序）只需 O(n)——内层循环一次都不执行。它稳定，且原地（只需 O(1) 额外空间）。移动次数恰好等于数组的逆序对数量。
图：插入排序在 [5,2,4,6,1,3] 上的第 1 趟归位过程
三、选择排序：每趟挑最小的放前面
选择排序的思想是"先挑最小的放最前"：在尚未排序的部分里找到最小元素，与未排序区的第一个位置交换；重复直到结束。它和插入排序的区别在于——插入是"把当前元素归位"，选择是"把当前位置该有的元素换过来"。
代码：
def selection_sort(a):
n = len(a)
for i in range(n):
m = i
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return a
复杂度：无论输入如何，比较次数恒为 n(n-1)/2，始终是 O(n²)；交换次数最多 n-1 次（比插入排序少很多）。但它是不稳定的——例如 [2ₐ, 2_b, 1]，第一轮把 1 换到最前，2ₐ 被推到 2_b 之后，相等元素的相对顺序被破坏。它同样原地、O(1) 空间。
图：选择排序第 1 趟——最小值 1 换到最前
四、冒泡排序：相邻比较，大的往右冒
冒泡排序反复扫描数组，比较相邻两个元素，若顺序不对就交换，于是每趟都会把当前未排序区里最大的元素"冒泡"到末尾。加上"某趟没有发生交换就提前结束"的优化后，最好情况也可达 O(n)。
代码：
def bubble_sort(a):
n = len(a)
for i in range(n):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
break
return a
它稳定、原地，但比较和交换都偏多，实践中最慢，主要作为教学示例与稳定性演示存在。
图：冒泡排序第 1 趟——最大值 6 冒泡到末尾
五、三者对比
| 排序 | 最坏 | 最好 | 稳定性 | 交换次数 | 特点 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n) | 稳定 | ≤逆序对 | 近乎有序时极快，适合在线数据 |
| 选择排序 | O(n²) | O(n²) | 不稳定 | ≤ n-1 | 交换少，但与输入无关地慢 |
| 冒泡排序 | O(n²) | O(n)* | 稳定 | 较多 | 教学用，演示稳定性 |
*含"无交换提前退出"优化时。
六、稳定性与适用场景
稳定性指相等元素的相对顺序在排序后保持不变。插入排序和冒泡排序稳定，选择排序不稳定。稳定性在多关键字排序中很关键：例如先按"分数"排、再按"姓名"排，若第二次排序不稳定，第一次的分数顺序就会被打乱。数据库与标准库的排序都格外看重这一点（Timsort 就是稳定排序）。
小结与下一步
O(n²) 三剑客是排序世界的"地基"：插入排序胜在近乎有序与小数组，选择排序交换最少，冒泡排序用于讲清稳定性。下一步建议推进：B2 归并排序（用分治把复杂度压到 O(n log n)）→ B4 堆排序（用堆结构原地 O(n log n)）→ B3 快速排序（平均最快，昨日 620 已铺垫）。整个排序轨道已在缺口体系中排好优先级，逐个击破即可。
---