NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 7 题

应用快速排序的分治思想，可以实现一个求第 $K$ 大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（ ）。

这题核心是快排的分治思想——选个基准数把数组一劈两半，如果第 K 大的数刚好落在哪一半，就只在那一半里继续找，另一半直接扔掉。别被排序的 O(n log n) 带偏，求第 K 大根本不用排完所有数。

最容易错在把“排序”和“找第 K 大”混为一谈，以为必须 O(n log n)；或者想到最坏情况 O(n²) 就慌了，忘了题目明确说了“不考虑极端最坏情况”。还有人会纠结空间复杂度，以为要额外开数组导致变 O(n)，其实原地划分的空间就是 O(1)。

考点：快速选择（Quickselect）算法及其平均时间复杂度。

概念：快速排序的核心是“分治”——选一个基准数（pivot），把数组分成比它小和比它大的两部分。快速选择就是把这个思想用在“找第 K 大”上：我们不需要把整个数组排好序，只需要把数组划分一次，看看第 K 大的数落在左边还是右边。如果落在左边，就只在左边继续划分；落在右边，就只在右边继续。这样每次只递归处理一半，另一半直接丢弃。

命题视角：出题人爱考“理论最优”和“最坏情况”的区别。这里明确说了“不考虑极端的最坏情况”，就是让你忽略 pivot 恰好选到最大或最小值导致划分极度不平衡的那种 O(n²) 情形，只考虑平均情况。很多学生看到“快速排序”就本能地回答 O(n log n)，那是排序的全局复杂度，不是找第 K 大的局部复杂度。

思考心法：拿到题先想——我要找第 K 大，快排第一步选 pivot 后，数组被劈成两段，pivot 自己的位置就是“第几大”。如果 K 等于 pivot 的位置，直接返回 pivot；如果 K 小于 pivot 位置，说明第 K 大在左边，递归左边；如果 K 大于，递归右边。每次递归前，数组大小从 n 变成 n/2 左右，所以总操作量是 n + n/2 + n/4 + ... = O(n)。

计算与避坑：平均情况下，每次划分都能把数组大致减半，递归深度是 O(log n)，每层处理 O(n) 个元素，但每层处理的元素总数加起来是等比数列，总和就是 O(n)。千万不要写成 O(n log n)，那是排序；也不要写 O(n²)，那是最坏情况。空间上，原地划分不需要额外数组，只是递归栈 O(log n)，题目问时间复杂度，所以答案是 O(n)。

考频与趋势：快速排序是题库的重磅考点，53 题覆盖 7 个级别，从 2008 到 2026 年年均约 4 题，近年（2024-2026）更是集中爆发，说明命题人持续偏爱这个知识点。求第 K 大是快排最经典的延伸应用，几乎年年都有变种考法。

预测：基于近年高频趋势，未来考题大概率会继续围绕“第 K 大 / 第 K 小”的局部复杂度展开，可能会结合随机化 pivot 或中位数取法来挖坑，但核心答案 O(n) 不会变。