NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 8 题

快速排序平均情况和最坏情况下的算法时间复杂度分别为：

这题考排序复杂度，核心是快速排序：平均 O(n log2 n)，最坏 O(n²)。拿到题先想基准划分是否均匀，再判断极端情况（已序/逆序）会导致多少次递归和比较。

学生常把平均 O(n) 当成快速排序，那是桶排/计数排；或以为最坏是 O(n log n)，那是归并/堆排。快速排序最坏其实是每次选到极值做基准，退化成冒泡式比较，所以是 O(n²)。

考点定位

本题只问快速排序的平均和最坏时间复杂度，属于经典分治算法复杂度记忆与推理题。命题人常把不同排序的“平均/最坏”混在一起挖坑，比如把 O(n) 平均强行安在快速排序上，或把 O(n log n) 最坏安在快速排序上，让你选错。

概念人话版

快速排序（Quick Sort）是 Hoare 1960 年提出的分治排序： 1. 选一个“基准”（pivot）； 2. 把数组一分为二：小于基准的去左边，大于基准的去右边（partition）； 3. 递归地对左右两段再重复上述步骤。

每次 partition 要把 n 个元素比较并移动，代价是 O(n)。总复杂度取决于“分了多少层”以及“每层一共处理多少个元素”。

平均情况：为什么是 O(n log2 n)？

当数据随机、基准划分比较均匀时，每层递归把当前规模 n 分成大约 n/2 和 n/2 两段，递归深度约为 log2 n。每层总共还是 O(n) 工作量，所以总的是 O(n log2 n)。这也是快速排序在竞赛里被当作“平均最优”的排序之一。

最坏情况：为什么退化成 O(n²)？

最坏发生在每次选到的基准都是当前段的最小值或最大值（比如数组已经从小到大排好，而你总选第一个或最后一个当基准）。这样 partition 后一边是空，另一边仍是 n-1，递归深度变成 n 层，每层 O(n)，合计 O(n²)。这和冒泡排序、插入排序的最坏复杂度同阶，但快速排序的平均表现远好于它们。

命题人怎么挖坑？

• 把“平均 O(n)”安在快速排序上，让你误选 B 或 C；
• 把“最坏 O(n log n)”安在快速排序上，让你误选 C 或 D；
• 把“稳定”这个属性混进来（快速排序不稳定），但本题未问，属于干扰项思维。

考频与趋势（基于给定数据）

题库共 53 题，覆盖 7 个级别（2008–2026）。逐年分布：2008 年 1 题、2009 年 3 题、2011 年 1 题、2012 年 1 题、2019 年 1 题、2020 年 1 题、2023 年 6 题、2024 年 15 题、2025 年 14 题、2026 年 7 题、null 年 3 题。分赛事：GESP 五级 29 题、GESP 八级 7 题、GESP 七级 5 题、NOIP 提高组 初赛 4 题、CSP 提高级 4 题、GESP 六级 2 题、NOIP 普及组 初赛 2 题。可见快速排序是高频考点，尤其在 GESP 五级和近年 NOIP/CSP 提高组/初赛，2024–2026 三年合计 26 题，说明命题人持续重视分治排序的复杂度辨析。

预测（基于数据与经验）

未来仍可能以“平均 vs 最坏”的对比形式出现，或把快速排序与归并/堆排序放在同一组选项里，让你区分稳定性与复杂度。暂无足够依据预测会突然转向其他排序（如桶排/计数排）的复杂度细节，因为题库里快速排序占比过高，短期大概率继续围绕它出题。