GESP 四级 · GESP 202412 C++ 四级 第 22 题

冒泡排序的平均时间复杂度为 $O(n^2)$，但最优情况下为 $O(n)$。

答案A。稳定排序保持相等元素的原始相对顺序。选择排序在交换时可能改变相等元素的相对位置，因此是不稳定的。

稳定排序的定义：相等元素排序后相对顺序不变。选择排序在交换时可能改变相等元素顺序，因此不稳定。

1. 🎯 考纲定位（考点定位）

《GESP C++算法与数据结构》第四章"排序与查找"，四级第3章。命题人专门卡住"平均时间复杂度"这一概念——绝大多数考生只会背"冒泡排序是O(n²)"，却分不清平均/最坏/最优的区别，导致看到"最优O(n)"就条件反射选B。

2. 🧠 解题思维（拆解与通法）

冒泡排序外层循环n-1轮，内层比较次数逐轮减1：第1轮n-1次，第2轮n-2次……第n-1轮1次。比较总次数 = (n-1)+(n-2)+…+1 = n(n-1)/2，故平均复杂度O(n²)。若输入已完全有序，内层每轮比较时未发生交换，可提前终止，比较次数≈n，最优复杂度O(n)。因此题干"平均O(n²)，最优O(n)"正确，选A。