题目

下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是( )。

① 插入排序　② 选择排序　③ 起泡排序　④ 希尔排序　⑤ 堆排序

错因

A

把"O(n²) 简单排序"和"链式效率会降低"画了等号。其实插入排序和选择排序都是顺序扫描"从头到尾"，没有"按下标随机跳跃"的需求——链式 / 顺序都能 O(n²) 跑完。把"链式 = 一切都慢"当成万能规律就会误选。

B

② 和 ③ 都不依赖随机访问：选择排序要的是"扫一遍找最小"，起泡排序要的是"扫一遍比较相邻"，两个动作链表都能直接做。误选可能是把"链表插入慢"和"链表比较慢"混淆——链表插入操作（断链/接链）反而不慢，慢的是跳转到任意下标。

C

判对了 ④（希尔排序确实因为按 gap 间隔访问而慢），但 ③ 起泡排序错。起泡的本质是相邻元素交换，链表里通过断链改指针就能交换两个相邻节点，时间复杂度仍是 O(n²)，没有恶化。漏掉了同样依赖随机访问的 ⑤（堆排序）才是关键失误。

总解析

判别核心：算法是否需要"按下标随机跳跃"。

顺序存储能 O(1) 算 a[i]、a[i+gap]、a[2i+1]——只要给个下标就能直达。换成链式存储后，要访问第 个节点需要从头走 步，O(1) 随机访问 → O(k) 顺序访问。哪些算法依赖随机跳跃，哪些不依赖，是这道题唯一的判据。

逐项分析：

排序	关键操作	依赖随机访问？	链式后效率
① 插入排序	顺序扫已排序段找位置 + 元素后移（链表是改指针）	否	不变
② 选择排序	顺序扫剩余段找最小 + 交换	否	不变
③ 起泡排序	顺序扫 + 相邻比较交换	否（相邻就在 next 指针处）	不变
④ 希尔排序	按增量 gap 跨步访问 a[i]、a[i+gap]	是	降低
⑤ 堆排序	完全二叉树按下标父子关系 a[i] ↔ a[2i+1] / a[2i+2]	是	降低

为什么 ④ 慢：希尔排序对每个 gap 做一遍"跨 gap 的插入排序"，需要从 a[i] 直接跳到 a[i+gap]。链表里跳 gap 步要 O(gap) 时间，外层再嵌入插入排序的循环，整体开销显著抬升。更糟的是，链表无法高效"按 gap 索引"，希尔排序的关键加速思想（部分有序后再小步整理）在链式上失去意义。

为什么 ⑤ 慢：堆排序依赖完全二叉树的隐式数组表示——下标 的左孩子是 、右孩子是 。链表里每次"找孩子"都要从根重新走一遍，向下调整一次堆就要 O(n) 而不是 O(log n)，整个堆排序退化到 O(n²) 级别甚至更慢。

只有 ④ 和 ⑤ 在链式存储下时间效率会下降。

最终答案是 D。

小结：判断"链式 vs 顺序"的效率差异，盯紧两件事——①算法是否需要随机访问下标，②比较 / 移动操作能否就地通过指针完成。两条都满足"无随机访问、操作可指针化"的算法（插入、选择、起泡）链式版本不会变慢；任一条不满足（希尔靠 gap 跳跃、堆靠下标父子关系）就会显著退化。