选取：通用算法
看完你能讲清快速选择如何在平均 O(n) 时间内找到第 k 大元素
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
选取：通用算法
看完你能讲清快速选择如何在平均 O(n) 时间内找到第 k 大元素
什么是选取问题
上一页我们看到：选第 k 大不必排序全部元素。就像找班里第 5 高的人，不需要给所有人排好队——你只关心那一个人是谁。这类「只挑不排」的问题，就叫选取问题。
「排队取第 5 名」对应排序法，「直接挑出那一个」对应选取算法
quickSelect 的算法流程
quickSelect 借快排划分，每轮只留一侧，候选区间逐步收缩。
quickSelect 代码实现
quickSelect 的完整 Python 实现，重点看递归为何只走一个分支。
每次划分后比较 k 与基准下标 p：相等即答案，否则只递归目标所在的一侧——这就是它比快排快的原因，均摊 O(n)。
quickSelect 的性能
上一页我们写出了 quickSelect 的代码——它不递归两边，只走一边，看起来比快排省事。但省事不等于稳定：走哪边、划分多均衡，全凭运气。
每次对半切只需一刀；总切偏则逼近逐粒挑
linearSelect 五步流程
linearSelect 五步走，用中位数的中位数保证每次划分都靠谱。
中位数的中位数
先看分组结构，再看每层如何缩小范围：从中位数的中位数出发，理解为何能保证够好的划分。
性能分析 A：递推式
上一页我们看到中位数的中位数能挑出好主元，但「好」到底好到什么程度？关键在于：主元把数组切开后，两边规模不能太大。这一页我们把它算成一笔账。
只沿着粗的枝干继续追，细的那半直接扔掉不砍
性能分析 B：递推求解
用等比级数收紧递推式：两项系数之和小于 1，总和被封在 O(n)。
性能分析 C：常数与改进
前面我们证明了 linearSelect 严格 O(n)，看起来完胜 quickSelect 的平均 O(n)。但大 O 只看增长趋势，把常数都抹掉了——而 linearSelect 恰恰藏着一个很大的常数。
外卖上不封顶但慢且贵，对应大 O 有保证但常数大
quickSelect vs linearSelect
两者都能期望线性选第 k 大，但一个靠概率、一个靠设计——混淆点在保证的强度不同。
- 期望 O(n)，随机主元实现简单
- 最坏 O(n²)，构造输入会退化
- 常数小，缓存友好，实测更快
- 严格 O(n)，理论有硬保障
- 最坏也是 O(n)，无退化风险
- 常数大，分组求中位数开销高
自测：主元质量
linearSelect 选取的中位数的中位数作为主元，最关键的保证是什么？
要点收束
- ✓选取只需递归一侧，期望 O(n) 即可达成
- ✓主元质量决定快选是否退化为 O(n²)
- ✓中位数的中位数保证线性最坏情况
- ✓确定性 O(n) 赢在最坏情况，常数却更大
- ✓实际数据常让 quickSelect 更快
课后思考
先自己想五分钟，再看参考答案——这些问题的价值在于想的过程。
参考答案线索：推导分组大小 g 的递推式 T(n)≤T(n/g)+T(3n/4)+O(n)，看 g=3 时 1/g 与 3/4 之和是否超过 1。5 恰好保证线性收敛，7 也行但每组找中位数更贵。
参考答案从极端输入入手：如果主元选择反复被对抗性数据打偏，quickSelect 退化到 O(n²)；对可预判恶意输入或需要严格最坏保证的系统，最坏线性时间本身就值这个常数。
参考答案它的本质是「确定性挑出质量有保证的分割点」。凡是依赖分割/剔除的问题都可借用，比如排序网络、平面最近点对的分界线选取、贪心删除类问题的批量筛除。