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

考虑最坏情况下冒泡排序算法的时间复杂度，$ T(n) $ 为待排序数字的数目为 $ n $ 的复杂度，则其递推关系式为 $ T(n) = T(n - 1) + n $，$ T(0) = 1 $。

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

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

【考点】递推关系式｜排序算法复杂度｜算法最坏情况

1. 🎯 考纲定位

GESP 四级 C++ 大纲的算法基础模块，考察递推关系式的构造能力。命题人专门卡住那些"背过冒泡排序是 O(n²) 但不会推导递推式"的考生——知道结果却说不清过程。