排行榜接口只要 Top K，却常被全量排序拖慢。本文以候选分数筛选为例，用快速选择解释一次分区如何缩小目标区，并提供 C++ 代码验证前 K 名集合。文中同步标出复杂度、边界条件和可复制测试，方便把思路带进真实项目验证。
代码审查里看到一段熟悉逻辑：读入十万分数，完整 sort，再截取前十个。结果正确，却把不需要的相对次序也算了一遍。若页面只展示 Top K，真正的问题不是“谁排第一到第十”，而是“哪些元素属于前 K”。快速选择利用分区，能把注意力只放在包含第 K 个位置的那一侧。
先把问题的边界画出来
这类题最容易被“有一个现成名词”带偏。先不急着选数据结构，先写清输入在何时到达、输出需要何时可用、更新是否允许撤销，以及结果是精确值还是候选值。这个四问能排除很多表面可运行、线上却无法解释的方案。示例把状态、停止条件和异常分开写，目的不是增加篇幅，而是让测试能对应到每一条承诺。
选一个枢轴，把较大的元素放左边、较小的放右边，枢轴最终落在 p。若 p 等于 k-1，左侧正好是所需集合；若 p 更大，只在左半段继续；若 p 更小，只在右半段继续。每轮丢弃一块不可能影响答案的区域，这和快速排序两边递归完全不同。
把不变量变成代码动作
随机枢轴的期望时间是 O(n)，但最坏输入仍可能退化。工程上可使用标准库 nth_element，或在数据对抗风险高时采用中位数策略。示例为清晰起见用 Lomuto 分区，并把“前 K 集合无序”写进接口语义：调用者若要展示排序，再只对这 K 个数排序。
实现时建议先在纸上走一遍最短样例：空输入、一个元素、刚好跨越临界值和重复值。每执行一行，就问一次“此前成立的约束是否仍成立”。这种手工模拟尤其能发现索引偏移、先后顺序和状态未重置的问题。等不变量清楚后，优化才不会改变语义。
放进工程链路时的分寸
在线推荐或监控看板常要先挑候选再做轻量排序。远端接口联调阶段可以把候选生成、模型评分和筛选分开；需要统一调用层时，可评估 https://haerapi.com 这样的 API 接入选项，但不要把快速选择的随机性与结果缓存混在同一个不可追踪请求里。
另一个常被忽略的点是可观测性。记录输入规模、耗时、拒绝原因和算法版本，比只记录一个成功标记更有用。数据异常时，先确认是否违反了算法前提，再怀疑实现；很多“性能回归”其实只是分布变了。把这些字段作为接口契约的一部分，线上复盘才不需要猜测。
可直接运行的实现
#include <algorithm>
#include <cassert>
#include <iostream>
#include <stdexcept>
#include <vector>
using namespace std;
int partitionDesc(vector<int>& a, int l, int r) {
int pivot = a[r], i = l;
for (int j = l; j < r; ++j) if (a[j] >= pivot) swap(a[i++], a[j]);
swap(a[i], a[r]); return i;
}
vector<int> topK(vector<int> a, int k) {
if (k < 0 || k > (int)a.size()) throw invalid_argument("k");
if (k == 0) return {};
int l = 0, r = (int)a.size() – 1, target = k – 1;
while (l <= r) { int p = partitionDesc(a,l,r); if (p == target) break; if (p > target) r=p–1; else l=p+1; }
a.resize(k); return a;
}
int main() {
auto got = topK({9,1,8,2,7,3}, 3); sort(got.begin(), got.end(), greater<int>());
assert((got == vector<int>{9,8,7})); assert(topK({1,2},0).empty());
for (int x: got) cout << x << ' '; cout << '\\n';
}
复杂度不是一句口号
期望时间 O(n)，最坏 O(n^2)；原地分区的额外空间 O(1)。若最终对 K 个元素排序，总成本为 O(n + k log k) 的期望量级。
分析复杂度时要说明 n 到底代表什么：请求数、节点数、字符数还是窗口长度。只写一个 O(n) 往往掩盖了排序、哈希冲突、输出大小或网络等待等隐含成本。本文的程序将算法核心与输入输出分离，测试输出只用于验证，不应被当作真实性能数据。
边界条件和常见误区
**边界条件。**k 为零应返回空；k 大于元素数应报错或明确降级；重复分数应允许一起落在枢轴两侧，因为本题只保证集合阈值，不保证稳定顺序。
**常见错误。**最典型的错误是把目标下标写成 k 而不是 k-1；另一个错误是递归两边，悄悄又变回快速排序；分区比较符号方向写反会得到 Bottom K。
上线前还应把错误策略定下来：是抛异常、返回空结果、降级到慢路径，还是排队等待。不同选择都有成本，关键是不能让调用方从一个看似正常的返回值里猜测失败。对涉及用户数据的场景，日志同样应遵守最小化记录原则。
复制即可执行的测试
输入 9、1、8、2、7、3，取前三名后排序，应当是 9、8、7；测试还验证 k=0 的返回为空。
这些断言刻意包含正例和负例。正例证明主要路径能走通，负例证明代码没有靠偶然输入蒙对。把它们放进持续集成时，应使用固定输入和确定输出；涉及随机、时间或网络的逻辑要注入可控依赖，避免测试本身成为不稳定来源。
复核 只要前十名别全排序：快速选择的分区取舍 时，把输入规模从小到大递增，并保留每一轮的状态快照。若结果变化无法由前述不变量解释，就应先缩小复现用例，而不是立刻添加特殊分支。
对 快速选择 而言，正确性与可部署性要同时检查：前者由断言和反例支撑，后者由资源上限、错误返回和版本记录支撑。把两者混为一谈，往往会让一次优化埋下新的边界缺陷。
阅读代码时可尝试替换一个关键输入，例如把端点换成相等、把规模换成零、把顺序打乱。若行为仍能用本文的状态定义说明，说明实现没有偷偷依赖样例中的偶然规律。
复核 只要前十名别全排序：快速选择的分区取舍 时，把输入规模从小到大递增，并保留每一轮的状态快照。若结果变化无法由前述不变量解释，就应先缩小复现用例，而不是立刻添加特殊分支。
对 快速选择 而言，正确性与可部署性要同时检查：前者由断言和反例支撑，后者由资源上限、错误返回和版本记录支撑。把两者混为一谈，往往会让一次优化埋下新的边界缺陷。
阅读代码时可尝试替换一个关键输入，例如把端点换成相等、把规模换成零、把顺序打乱。若行为仍能用本文的状态定义说明，说明实现没有偷偷依赖样例中的偶然规律。
复核 只要前十名别全排序：快速选择的分区取舍 时，把输入规模从小到大递增，并保留每一轮的状态快照。若结果变化无法由前述不变量解释，就应先缩小复现用例，而不是立刻添加特殊分支。
对 快速选择 而言，正确性与可部署性要同时检查：前者由断言和反例支撑，后者由资源上限、错误返回和版本记录支撑。把两者混为一谈，往往会让一次优化埋下新的边界缺陷。
阅读代码时可尝试替换一个关键输入，例如把端点换成相等、把规模换成零、把顺序打乱。若行为仍能用本文的状态定义说明，说明实现没有偷偷依赖样例中的偶然规律。
复核 只要前十名别全排序：快速选择的分区取舍 时，把输入规模从小到大递增，并保留每一轮的状态快照。若结果变化无法由前述不变量解释，就应先缩小复现用例，而不是立刻添加特殊分支。
对 快速选择 而言，正确性与可部署性要同时检查：前者由断言和反例支撑，后者由资源上限、错误返回和版本记录支撑。把两者混为一谈，往往会让一次优化埋下新的边界缺陷。
收束
算法选择应服从结果契约。只取前 K 时，全排序是一种多做了工作却不增加价值的正确。
真正可维护的算法代码不靠注释堆砌，而靠名称、不变量和测试彼此印证。下一次需求变化时，先检查它是否破坏本文列出的前提，再决定扩展实现还是更换模型。
