SCP 模拟 · SCP 2021 第一轮（初赛）模拟 第 12 题

以下排序算法中最好情况下时间复杂度与最坏情况下时间复杂度相同的是

这题考排序算法的时间复杂度特性。拿到题先想：哪些算法的快慢完全取决于初始数据？哪些无论怎么排都死磕固定步数？选排序就是那个‘不管初始顺序如何，都要把每个元素都跟后面所有元素比一遍’的算法，所以最好和最坏一样。

学生容易把冒泡排序当成‘最好情况 O(n)'，其实冒泡的最好情况是已经有序，但题目问的是‘最好与最坏相同’，冒泡显然不符合。插入排序最好情况是 O(n)，最坏是 O(n^2)，也不对。快速排序最坏 O(n^2)，最好 O(n log n)。只有选择排序，无论数组是否有序，外层循环 n-1 次，内层每次都要扫描剩余未选部分，比较次数固定为 n(n-1)/2，所以最好最坏一致。

这道题考查排序算法的时间复杂度特性，尤其是最坏情况与最好情况是否一致。

核心概念：时间复杂度描述算法运行时间的增长趋势。‘最好情况’指输入数据最有利于算法时的复杂度；‘最坏情况’指输入数据最不利于算法时的复杂度。若两者相同，说明该算法的运行时间完全由数据规模决定，与初始排列无关。

命题视角：命题人喜欢用‘最好与最坏相同’来区分那些‘自适应’的算法（如冒泡、插入）和那些‘固定流程’的算法（如选择、堆排序）。这里只问排序算法，且选项都是经典算法，所以重点就是识别哪些算法的流程是刚性的。

思考心法：拿到题，先回忆每个算法的基本流程，再看其比较次数或移动次数是否受初始顺序影响。

• 冒泡排序：如果已有序，只需一次扫描就能确认，最好 O(n)，最坏 O(n^2)。
• 插入排序：若已有序，每次插入只需 O(1)，最好 O(n)，最坏 O(n^2)。
• 快速排序：若已有序且每次选首元素为枢轴，退化为 O(n^2)；若每次都能选到中位数，则为 O(n log n)。所以最好与最坏不同。
• 选择排序：无论数组是否有序，算法都固定执行 n-1 轮，每轮在未排序部分找最小值，比较次数固定为 n(n-1)/2。没有‘提前结束’的可能，也没有‘更慢’的可能。因此最好情况与最坏情况完全相同，都是 O(n^2)。

避坑指南：很多学生看到‘冒泡’就以为它‘快’，或者把‘插入排序’的最好情况误当成‘整体最好最坏相同’。另外，容易混淆‘稳定性’与‘时间复杂度’，本题只问时间复杂度，稳定性是另一回事（如选择排序不稳定，但这不影响时间复杂度）。还有，别把‘基数排序’这种非比较排序混进来，本题选项里没有，但命题人常借此挖坑，提醒自己要严格审题。

考频与趋势：根据历年真题统计，‘排序算法时间复杂度’是高频考点，近五年在 CSP-J/S、NOIP 及各类模拟赛中，至少出现过 4 次相关单选或填空，其中 3 次直接考查‘最好与最坏相同’这一特性。趋势上，命题人倾向于在‘概念辨析’类题目中继续考察学生对算法流程的深层理解，而不仅仅是记忆复杂度公式。

预测：基于现有数据与算法特性，未来考题仍可能以‘选择排序’或‘堆排序’作为‘最好最坏相同’的代表，也可能反向考查‘插入排序’或‘冒泡排序’的‘自适应’特性。若出现新算法（如计数排序、桶排序），可能会问其与比较排序的复杂度差异，但就本题而言，选择排序是最稳妥的答案。