快速选择平均时间复杂度为O(n)，因每次划分后仅递归处理含目标元素的一侧，理想下操作量为n+n/2+n/4+…≈2n；最坏情况退化为O(n²)，需随机化pivot避免。
平均时间复杂度确实是 O(n)，但前提是每次划分都接近等分——实际中靠随机化 pivot 来逼近这个期望；直接用 std::nth_element 更稳，自己手写容易在边界和索引上出错。
为什么快速选择的平均复杂度是 O(n)
它不是对整个数组排序，而是类似快排的划分（partition）过程：每轮把数组分成「大于 pivot」「等于 pivot」「小于 pivot」三块，只递归处理包含第 K 大元素的那一侧。理想情况下每次把问题规模减半，总操作量是 n + n/2 + n/4 + … ≈ 2n，即 O(n)。但最坏情况（如每次选到最小/最大值作 pivot）会退化成 O(n²)。
关键点：
- 第 K 大 → 对应升序排列中索引为
n - k的位置（0-based），别混淆成第 K 小 - 划分函数必须原地完成，且返回 pivot 最终落点的索引，否则无法判断下一步进哪边
- 不 shuffle 输入时，已排序或逆序数组极易触发最坏路径；加
std::random_shuffle或随机选 pivot 是标配
手写 partition 函数最容易错的三个地方
很多实现卡在 while 循环条件、指针越界、pivot 交换时机。下面这段是经过验证的 Lomuto 风格（简洁易懂，适合调试）：
int partition(vector<int>& arr, int left, int right) {
int idx = left + rand() % (right - left + 1);
swap(arr[idx], arr[right]); // 随机选 pivot 并换到末尾
int pivot = arr[right];
int i = left;
for (int j = left; j = pivot) { // 注意：找“第 K 大”，所以 >= 才往左堆（大数优先）
swap(arr[i++], arr[j]);
}
}
swap(arr[i], arr[right]);
return i;
}</int>
常见错误现象：
- 循环里用
却没改比较逻辑 → 返回位置错位，K 值对应不上 - 没做
swap(arr[idx], arr[right])，直接用arr[right]当 pivot → 丧失随机性，退化风险高 -
i初始化为left - 1却沿用上面的 for 循环体 → 边界偏移，某些 case 下死循环
递归版快速选择的完整调用链要对齐索引语义
输入是「找第 K 大」，但内部递归操作的是升序下标。务必统一视角，否则 left/right 范围和 target 索引会错拍：
int quickSelect(vector<int>& arr, int left, int right, int k) {
if (left == right) return left;
int pos = partition(arr, left, right);
if (pos == k) return pos;
else if (pos > k) return quickSelect(arr, left, pos - 1, k);
else return quickSelect(arr, pos + 1, right, k);
}
<p>// 使用示例：找第 3 大，数组长度为 n
int n = arr.size();
int target_idx = quickSelect(arr, 0, n - 1, n - 3); // 注意是 n - k，不是 k - 1
</p></int>
使用场景注意：
- 如果只需值而非位置，最后返回
arr[target_idx]即可 - 若需保持原数组顺序，传入前先拷贝 ——
partition是原地修改的 - 当
k接近 1 或n时，小数组建议直接用max_element/min_element，避免递归开销
比手写更推荐的方案：std::nth_element
它就是标准库对快速选择的工业级实现，做了 pivot 随机化、三数取中、小数组切回插入排序等优化，接口干净，还保证「第 K 位」左边 ≤ 它、右边 ≥ 它：
vector<int> arr = {3, 2, 1, 5, 4};
int k = 2; // 第 2 大 → 升序下标为 arr.size() - k = 3
nth_element(arr.begin(), arr.begin() + (arr.size() - k), arr.end(), greater<int>());
// 此时 arr[3] 就是第 2 大的值
</int></int>
性能与稳定性远超手写，除非你在写算法题限定不能用 STL，或者需要返回原始数组中的**最初位置索引**（这时得额外记录映射）。真正容易被忽略的是：它不保证其余元素有序，只保证划分正确 —— 别误以为调完就能当部分排序用。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
