CSP-S 提高级 · CSP 2023 提高级第一轮 第 10 题

假设快速排序算法的输入是一个长度为n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

这题核心就是看 pivot 选首元素时，已排序数组会触发什么极端情况。拿到题先想：有序数组里第一个数最小，分治后左边永远空、右边只剩 n−1，递归深度直接拉满到 n，每层比较次数递减，加起来就是平方级，所以时间复杂度 Θ(n²)。

最容易犯的错是凭直觉选 B（Θ(n log n)），把平均情况和最坏情况混为一谈；或者觉得数组已排好序反而更快，选 A；还有人以为快速排序对已排序数组失效，选 D。这些坑都源于没抓住“首元素做 pivot + 已排序”这一组合带来的极端不平衡分割，导致递归树退化成一条线，比较次数从 n log n 飙到 n²。

这道题考查快速排序在最坏情况下的时间复杂度，特别聚焦于输入已排序且基准元素固定为第一个元素时的表现。快速排序的核心是分治：选一个基准（pivot），把数组分成小于等于 pivot 和大于 pivot 的两部分，然后递归排序。当数组本身已经升序排列，而算法每次都选第一个元素作为 pivot 时，第一个元素就是当前区间的最小值，划分后左侧部分为空，右侧部分只剩下 n−1 个元素。这意味着每一层递归只减少了一个元素，递归深度直接达到 n，整个递归树退化成了单条线。每层需要进行的比较次数分别是 n−1、n−2、…、1，总和为 n(n−1)/2，即 Θ(n²)。命题人喜欢在这里挖坑，就是利用学生默认快速排序平均是 Θ(n log n) 的惯性思维，或者误以为已排序对快速排序有利。避坑关键在于记住：快速排序遇到已排序数组且 pivot 固定为端点时，必然退化到最坏情况。实际应用中为了避免这种情况，常用随机选 pivot 或三数取中法，C++ 的 std::sort 更是采用内省排序（IntroSort），检测到递归过深时切换到堆排序。历年数据来看，快速排序在题库中已考过 53 题，覆盖 7 个考试级别，其中 2023 年考了 6 题、2024 年 15 题、2025 年 14 题、2026 年 7 题，可见该考点热度持续攀升，尤其是提高级和 GESP 八级、七级。基于趋势，未来几年这类“已排序 + 固定 pivot”的最坏情况分析题仍会高频出现，甚至可能结合其他排序算法对比出题。因此，看到“快速排序 + 已排序数组 + 首元素 pivot”三件套，条件反射选 Θ(n²) 就是稳操胜券。