快速选择算法 C++ 标准库函数：nth_element
👨💻 关于作者：会编程的土豆
“不是因为看见希望才坚持，而是坚持了才看见希望。”
你好，我是会编程的土豆，一名热爱后端技术的Java学习者。
📚正在更新中的专栏：
《数据结构与算法》😊😊😊
《leetcode hot 100》🥰🥰🥰🤩🤩🤩
《数据库mysql》
💕作者简介：后端学习者
先看例题：
class Solution { public: int findKthLargest(vector<int>& nums, int k) { nth_element(nums.begin(), nums.end() - k, nums.end()); return nums[nums.size() - k]; } };对，就是这么简单，完了，而且速度极快，时间复杂度为O(n)；
下面仔细阐述一下这个库函数：
nth是"n-th"的缩写，意思是"第 n 个"。
拆解
n：表示一个整数序号
th：英语序数词后缀（如 4th, 5th, 6th）
合起来 n-th：第 n 个
在函数名中的含义
std::nth_element直译就是"第 n 个元素"。
它的作用是：把容器中如果完全排序后，应该排在第 n 个位置的那个元素放到第 n 个位置。
下标从0开始的哦
作用把第二个参数表示的那个位置 "应该排在那个位置的元素"放过去，且不保证其他元素有序。
nth_element(nums.begin(), nums.end() - k, nums.end()); // ↑ ↑ ↑ // 起始迭代器 目标位置迭代器 结束迭代器nums.end() - k就是倒数第 k 个位置因为是升序排序，倒数第 k 个位置就是第 k 大的元素所在的位置
举例
数组[3,2,1,5,6,4]，k = 2：
完全排序后是
[1,2,3,4,5,6]第 2 大是 5，在倒数第 2 个位置（下标 4）
nth_element后数组变成类似[3,2,1,4,5,6]（不唯一）下标 4 的元素必定是 5
复杂度
| 维度 | 复杂度 |
|---|---|
| 时间 | 平均 O(n)，最坏 O(n²)（但标准库通常用 Introselect 保证 O(n)） |
| 空间 | O(1) |
其他语言的类似函数
| 语言 | 等价函数 |
|---|---|
| C++ | std::nth_element |
| Python | heapq.nlargest(k, nums)[-1]或sorted(nums)[-k] |
| Java | Arrays.sort(nums); return nums[nums.length - k]; |