Quick Select核心是三路划分分区并递归处理目标区间，平均O(n)、最坏O(n²)；需随机化pivot防退化，partition返回等于pivot区间的左边界，k为0-based下标。
Quick Select 的核心逻辑是啥
它不是排序，而是用类似快排的分区（partition）思路，每次把数组划成三块：小于 pivot、等于 pivot、大于 pivot，然后只递归处理可能包含第 k 小元素的那一侧。平均时间复杂度 O(n)，最坏 O(n²)（比如每次都选到最小/最大值当 pivot），但实践中加随机化后几乎不会退化。
怎么写一个靠谱的 partition 函数
别直接套教科书上的双指针“Lomuto”版本——它在大量重复元素时性能差，还容易因边界错位导致越界。推荐用三路划分（Dutch National Flag 风格），尤其适合含重复值的场景：
int partition(vector<int>& arr, int left, int right, int pivot_idx) {
int pivot = arr[pivot_idx];
swap(arr[pivot_idx], arr[right]);
int lt = left, gt = right;
int i = left;
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr[lt++], arr[i++]);
} else if (arr[i] > pivot) {
swap(arr[i], arr[gt--]);
} else {
i++;
}
}
return lt; // 第一个等于 pivot 的位置
}-
pivot_idx必须在[left, right]范围内，否则swap会崩 - 返回值不是 pivot 最终下标，而是「等于 pivot 区间的左边界」，这对后续跳过重复块很关键
- 别漏掉
i++在arr[i] == pivot分支里，否则死循环
递归调用时怎么缩小区间
关键是根据 k 和三段长度关系决定下一步查哪边。设 lt 是 partition 返回值，gt + 1 是等于 pivot 区间的右边界（闭区间为 [lt, gt]）：
- 如果
k < lt：第k小在左边小块，递归[left, lt - 1] - 如果
k > gt：在右边大块，递归[gt + 1, right] - 否则
k落在[lt, gt]内，直接返回arr[k]（此时所有arr[lt..gt]都等于 pivot，且位置已就绪）
注意：k 是 0-based 索引。求第 K 小元素时，传入的 k 应为 K - 1，别在递归里反复减 1，容易混乱。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
为什么必须加随机化 pivot
不随机的话，对已排序或逆序数组，每次选 right 当 pivot，就会退化成 O(n²)。实操中只需一行：
swap(arr[pivot_idx], arr[left + rand() % (right - left + 1)]);
- 必须在调用
partition前做，且pivot_idx是你打算传给partition的那个索引 - 别用
rand() % n直接生成 pivot 下标再传进去——这样没解决 worst case，只是换了个固定偏移 - 如果用 C++11+，优先用
std::random_device+std::mt19937，但竞赛或快速验证时rand()加srand(time(0))也够用
真正难的不是写对逻辑，而是记住：partition 后不能假设 pivot 落在 k 位置；三路划分返回的是区间起点，不是单点；以及，k 是下标，不是排名——这三个点错一个，结果就全偏了。
