1. 三个算法的共同目标
冒泡、选择和插入排序容易手工跟踪，适合学习循环不变式。以下函数都原地修改列表，并返回同一个列表；key 只提取比较键。最坏时间均为 O(n²)，但工作方式和稳定性并不相同。
2. 冒泡：让最小值向左浮
按原文方向，从右向左比较相邻元素，逆序时交换。第一轮后最小值到索引 0，下一轮固定第二小值。相等键不交换，所以保持稳定。changed 是教学改进：一轮无交换即可提前结束。
3. 冒泡的 Python 实现
def bubble_sort(a, key=lambda x: x):
for i in range(len(a)-1):
changed = False
for j in range(len(a)-1, i, -1):
if key(a[j-1]) > key(a[j]):
a[j-1], a[j] = a[j], a[j-1]
changed = True
if not changed:
break
return a
输入 [3, 1, 2]，第一轮从右比较 1、2 不动，再交换 3、1，得到 [1, 3, 2]。第二轮交换 3、2。
4. 选择：扫描后只交换一次
第 i 轮在 [i, n) 找最小值，和 a[i] 交换。已固定前缀包含最小的 i 个元素。比较次数始终是 n(n-1)/2，非自交换最多 max(0, n−1) 次；有序输入也仍需完整扫描。
5. 选择排序实现与不稳定反例
def selection_sort(a, key=lambda x: x):
for i in range(len(a)-1):
smallest = i
for j in range(i+1, len(a)):
if key(a[j]) < key(a[smallest]):
smallest = j
if smallest != i:
a[i], a[smallest] = a[smallest], a[i]
return a
对 [2A, 2B, 1X]，首次把 1X 与 2A 交换，得到 [1X, 2B, 2A]，相等键顺序被反转。因此原文“交换式选择排序稳定”需要纠正。
6. 稳定的选择变体
def stable_selection_sort(a, key=lambda x: x):
for i in range(len(a)-1):
smallest = i
for j in range(i+1, len(a)):
if key(a[j]) < key(a[smallest]):
smallest = j
item = a[smallest]
for j in range(smallest, i, -1):
a[j] = a[j-1]
a[i] = item
return a
把选中的最小值暂存，再把中间记录右移，最后写入，避免跨越式交换打乱相等键。仍为 O(n²)，但不再保留普通选择排序的少移动优势。
7. 插入：维护有序前缀
从第二项开始，暂存当前 item，将前缀里严格大于 item 的记录右移，再填入空位。这与整理扑克牌相似。使用 > 而不是 >=，可让新来的相等键留在旧记录之后。
8. 插入排序的 Python 实现
def insertion_sort(a, key=lambda x: x):
for i in range(1, len(a)):
item = a[i]
j = i
while j > 0 and key(a[j-1]) > key(item):
a[j] = a[j-1]
j -= 1
a[j] = item
return a
对 [3, 1, 2]，插入 1 后 [1, 3, 2]；插入 2 时先右移 3，再填回 2。移动期间数组会暂时出现重复引用，暂存 item 保证没有丢失元素。
9. 复杂度和近乎有序数据
| 算法 | 最好 | 平均/最坏 | 稳定 | 工作空间 |
|---|---|---|---|---|
| 优化冒泡 | O(n) | O(n²) | 是 | O(1) |
| 交换式选择 | O(n²) | O(n²) | 否 | O(1) |
| 插入 | O(n) | O(n²) | 是 | O(1) |
插入排序的移动次数等于逆序对数 I，总工作可写为 O(n+I)。空列表、单项和全相等数据均应正确处理。
10. 可直接运行的例子
a = [20, 6, 55, 74, 3, 45, 13, 87, 46, 30]
print(insertion_sort(a.copy()))
records = [(2, "A"), (2, "B"), (1, "X")]
print(selection_sort(records.copy(), key=lambda r: r[0]))
print(stable_selection_sort(records.copy(), key=lambda r: r[0]))
三个算法各用一份副本，避免先排序后的数据影响后续实验。比较计数不能拿“交换数”和“写入数”直接混用。