GESP 五级 · GESP 五级样题（C++ 组） 第 12 题

下面 C++ 代码用于排序，下列说法中错误的是（ ）。 

这题考的是排序算法的时间与空间复杂度辨析。拿到题先看sortA和sortB分别是什么算法，再结合最好、最坏、平均三种情况去匹配选项，尤其要警惕把O(N)和O(log N)搞混。

很多学生看到两层循环就下意识认为是O(N²)，忽略了插入排序在最好情况下的线性特性。还有人会把归并排序的O(log N)空间复杂度套用到原地排序上，或者误以为平均情况也是O(log N)。选D时容易只盯着‘最坏是O(N²)'这一半对的话，却忽略了前半句‘平均和最好都是O(log N)'完全错误。

本题对应 GESP 五级「算法与数据结构」模块，核心考察排序算法复杂度辨析。命题人卡住的是考生对「原地排序」与「渐近复杂度」的混淆——很多学生看到两层循环就默认 O(N²)，却忽略了边界条件。先识别算法：sortA 是冒泡排序（双层循环，相邻比较交换），sortB 是插入排序（外层构建有序前缀，内层插入）。冒泡排序无论输入如何，外层循环固定执行 N-1 次，内层循环最少执行 N-1 次，故最好与最坏均为 O(N²)。插入排序已有序时内层循环 0 次，最好情况 O(N)；平均/最坏均为 O(N²)；空间复杂度两者均为 O(1)（原地排序）。A 项看似正确，但考生易忽略平均复杂度差异（插入排序平均仍为 O(N²)），误判为「不同」。B 项「一致」是绝对化表述，但两者确实同属原地排序，正确。C 项冒泡排序时间复杂度特性符合事实，正确。D 项最阴险：插入排序最好情况是 O(N) 而非 O(log N)，平均也不是 O(log N)，命题人用「都是 O(log N)」这种绝对化表述，专坑只背结论的学生。若把 sortB 改成归并排序或快速排序，D 项描述可能变为正确。刷到类似题时，先问自己：「命题人想考我什么？」——本题考的是对原地排序算法的「时间复杂度边界」与「空间复杂度」的精确区分。从考频看，排序基础在题库共考过 249 题，覆盖 9 个考试级别，逐年分布：2008 年 2 题、2009 年 3 题、2010 年 3 题、2011 年 1 题、2012 年 2 题、2013 年 1 题、2014 年 2 题、2015 年 1 题、2017 年 2 题、2018 年 1 题、2019 年 1 题、2020 年 2 题、2021 年 3 题、2022 年 5 题、2023 年 22 题、2024 年 51 题、2025 年 57 题、2026 年 50 题、null 年 40 题；分赛事：GESP 五级 74 题、CSP 入门级 44 题、GESP 四级 39 题、GESP 八级 27 题、GESP 七级 26 题、GESP 六级 12 题、NOIP 提高组 初赛 12 题、CSP 提高级 9 题、NOIP 普及组 初赛 6 题。sort 排序在题库共考过 128 题，覆盖 5 个考试级别，逐年分布：2011 年 1 题、2023 年 18 题、2024 年 39 题、2025 年 42 题、2026 年 18 题、null 年 10 题；分赛事：GESP 五级 67 题、GESP 八级 26 题、GESP 七级 22 题、GESP 六级 12 题、NOIP 提高组 初赛 1 题。复杂度分析在题库共考过 39 题，覆盖 2 个考试级别，逐年分布：2026 年 11 题、null 年 28 题；分赛事：CSP 入门级 38 题、CSP 提高级 1 题。暂无足够依据预测未来具体考法，但可关注原地排序与渐近复杂度的结合命题趋势。正确答案：D。