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 < right) {
int pivot_idx = left + rand() % (right - left + 1);
std::swap(nums[pivot_idx], nums[right]);
int mid = partition(nums, left, right);
if (mid == k) return nums[mid];
else if (mid > k) right = mid - 1;
else left = mid + 1;
}
return nums[left];
}
partition 函数里最容易错的三个细节
不是所有 partition 实现都等价。C++ 中若用 < 判定，返回的 pivot 位置必须满足：左边 ≤ pivot，右边 ≥ pivot，否则二分逻辑会漏掉边界元素。
立即学习“C++免费学习笔记（深入）”；
- 循环变量用
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 < right; ++j) {
if (nums[j] <= pivot) {
std::swap(nums[i], nums[j]);
++i;
}
}
std::swap(nums[i], nums[right]);
return i;
}调用时绕不开的边界和类型陷阱
k 是“第K大”，但数组索引从 0 开始，且 vector.size() 返回 size_t —— 混用 signed/unsigned 会导致静默翻转（比如 k=1 时 n-k 变成极大正数）。
- 统一用
int接收k，计算目标下标前强转：int target = static_cast<int>(nums.size()) - k; - 检查
k是否越界：if (k < 1 || k > nums.size()) throw std::out_of_range("k out of range"); - 单元素数组或空数组必须提前处理，否则
rand() % 0是未定义行为 - 如果编译器没开
-stdlib=libc++或 Windows 下，srand(time(0))只需调一次，别塞进函数里反复调
快速选择真正难的不是算法本身，而是 pivot 随机化是否生效、边界是否全覆盖、以及 signed/unsigned 类型混用带来的隐性崩溃 —— 这些地方一错，结果可能偶尔对、偶尔错，极难复现。
