12 简单排序算法
冒泡、选择、稳定选择和插入
第 01 题 问题 1
教材右向左冒泡对 [3,1,2] 完成第一轮后是什么？
参考答案
[1,3,2]。
解析
先比较 1、2 不换；再比较 3、1 并交换，最小值浮到最左。
第 02 题 问题 2
优化冒泡何时可以提前结束？
参考答案
完整一轮没有发生任何交换。
解析
所有待处理相邻项均已满足顺序；changed 标记应在每轮开始重置。
第 03 题 问题 3
选择排序对 n=5 的列表进行多少次键比较？
参考答案
10 次。
解析
4+3+2+1=5×4/2；本教材实现不因已有序而提前结束。
第 04 题 问题 4
选择排序对 n≥1 的列表最多多少次非自交换？
参考答案
n−1 次。
解析
每轮最多交换一次，最小值本就在当前位置时可不交换。
第 05 题 问题 5
交换式选择排序对 [2A,2B,1X] 的第一轮结果是什么？
参考答案
[1X,2B,2A]。
解析
1X 与 2A 跨位置交换，打乱 2A、2B 的原相对顺序，是不稳定反例。
第 06 题 问题 6
把最小项取出并右移中间记录的选择变体为什么稳定？
参考答案
不采用跨越交换，并选择第一个最小值。
解析
右移保持其余记录相对次序，最小值插回固定位置；代价是更多写入。
第 07 题 问题 7
插入排序 [3,1,2]，处理到索引 1 后是什么？
参考答案
[1,3,2]。
解析
暂存 1，右移 3，再把 1 填到索引 0。
第 08 题 问题 8
插入排序中把 > 改成 >=，稳定性会怎样？
参考答案
一般会失去稳定性。
解析
新来的相等键会跨到旧相等键之前；稳定实现只移动严格较大的项。
第 09 题 问题 9
升序输入上的插入排序复杂度及移动次数是什么？
参考答案
时间 O(n)，右移次数为 0。
解析
每个 item 与前项比较一次即可；仍有外层循环与填回操作。
第 10 题 问题 10
逆序 n=4 的插入排序右移次数是多少？
参考答案
6 次。
解析
每对元素都形成逆序对，3+2+1=6。不把填回 item 的写入混在右移次数里。
第 11 题 问题 11
冒泡、选择、插入在教材中的稳定性分别是什么？
参考答案
稳定、不稳定、稳定。
解析
冒泡只交换严格逆序相邻项；选择有跨越交换；插入只移动严格较大项。
第 12 题 问题 12
“三者都是 O(n²)，所以对近乎有序数据没有区别”对吗？
参考答案
不对。
解析
插入工作量可按 O(n+I) 描述，I 为逆序对数；选择仍进行固定数量比较。