quickselect 比 std::sort 更适合找第k大元素，因其平均时间复杂度为 o(n)，不排序只保证第k位就位；而 std::sort 为 o(n log n)。
为什么 quickselect 比 std::sort 更适合找第K大元素
因为排序整个数组是 O(n log n)，而 quickselect 平均只要 O(n) —— 它不排序，只保证第K位“就位”。实际中，当 K 接近 1 或 n（比如找最大、最小、前3大），quickselect 常比堆或排序快得多，尤其数据量大且不要求稳定时。
但注意：最坏情况是 O(n²)，发生在每次选的 pivot 都是最小/最大值。所以必须随机化 pivot，否则退化成冒泡级性能。
怎么写一个健壮的 quickselect（C++ 版本）
核心是复用 partition 逻辑，但只递归处理含目标索引的那一侧。C++ 中推荐用迭代写法避免栈溢出，或至少加尾递归优化。
- 输入数组建议传引用，避免拷贝；若不能修改原数组，先
std::vector拷贝一份 - 第K大 → 转为找“升序下标为
n - k”的元素（0-indexed），别硬写降序比较 - partition 用 Lomuto 方式更易懂，但 Hoare 更省交换次数；实践中 Lomuto + 随机 pivot 足够稳
- 务必在 partition 前 swap 一次随机位置到末尾，否则
std::vector的有序输入会触发最坏情况
int quickselect(std::vector<int>& nums, int left, int right, int k) {
while (left k) right = mid - 1;
else left = mid + 1;
}
return nums[left];
}</int>
partition 函数里最容易错的三个细节
不是所有 partition 实现都等价。C++ 中若用 判定，返回的 pivot 位置必须满足：左边 ≤ pivot，右边 ≥ pivot，否则二分逻辑会漏掉边界元素。
- 循环变量用
i和j时，别混淆 “已处理区间” 和 “待扫描区间” 的闭开关系 - swap 后
i必须自增，否则重复比较同一元素（常见 off-by-one） - 最后 swap
nums[i]和nums[right]时，要确认i是第一个 ≥ pivot 的位置 —— 这决定了返回值是否能准确划分区间
int partition(std::vector<int>& nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j <h3>调用时绕不开的边界和类型陷阱</h3>
<p><code>k</code> 是“第K大”，但数组索引从 0 开始，且 <code>vector.size()</code> 返回 <code>size_t</code> —— 混用 signed/unsigned 会导致静默翻转（比如 <code>k=1</code> 时 <code>n-k</code> 变成极大正数）。</p>
<ul>
<li>统一用 <code>int</code> 接收 <code>k</code>，计算目标下标前强转：<code>int target = static_cast<int>(nums.size()) - k;</int></code>
</li>
<li>检查 <code>k</code> 是否越界：<code>if (k nums.size()) throw std::out_of_range("k out of range");</code>
</li>
<li>单元素数组或空数组必须提前处理，否则 <code>rand() % 0</code> 是未定义行为</li>
<li>如果编译器没开 <code>-stdlib=libc++</code> 或 Windows 下，<code>srand(time(0))</code> 只需调一次，别塞进函数里反复调</li>
</ul>
<p>快速选择真正难的不是算法本身，而是 pivot 随机化是否生效、边界是否全覆盖、以及 signed/unsigned 类型混用带来的隐性崩溃 —— 这些地方一错，结果可能偶尔对、偶尔错，极难复现。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
