nth_element函数——C++快速选择函数
目录
1. 函数原型
2. 功能描述
3. 算法原理
4. 时间复杂度
5. 空间复杂度
6. 使用示例
8. 注意事项
9. 自定义比较函数
11. 总结
nth_element是 C++ 标准库中提供的一个算法，位于<algorithm>头文件中，用于部分排序序列。它的主要功能是将序列中第 k 小的元素放到第 k 个位置上，并且保证所有在它之前的元素都不大于它，所有在它之后的元素都不小于它。这个算法的核心思想是基于快速排序的分区操作（Quickselect）。
1. 函数原型
nth_element 的函数原型如下：
template <class RandomIt>
void nth_element(RandomIt first, RandomIt nth, RandomIt last);
template <class RandomIt, class Compare>
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);
first：指向序列起始位置的随机访问迭代器。
nth：指向序列中第 k 个位置的随机访问迭代器。
last：指向序列结束位置的随机访问迭代器。
comp（可选）：自定义比较函数，默认是std::less（升序）。
2. 功能描述（无返回值）
（补充：第k大对应第n-k小，对应的下标为n-1-k）
nth_element 的功能是将序列中第 k 小（对应数组下标为k-1）的元素放到第 k 个位置上，并且保证：
-
所有在第 k 个位置之前的元素都不大于第 k 个位置的元素。
-
所有在第 k 个位置之后的元素都不小于第 k 个位置的元素。
3. 算法原理
nth_element 的实现基于快速选择算法（Quickselect），它是快速排序算法的一个变种。其主要步骤如下：
选择支点：从序列中选择一个元素作为支点（pivot）。
分区操作：将序列分为两部分：
小于等于支点的元素放在支点的左边。
大于支点的元素放在支点的右边。
递归处理：
如果支点的位置恰好是 k，则支点就是第 k 小的元素。
如果支点的位置小于 k，则在右边的子序列中递归处理。
如果支点的位置大于 k，则在左边的子序列中递归处理。
4. 时间复杂度
平均时间复杂度：O(n)。
最坏时间复杂度：O(n2)，但这种情况很少发生，可以通过随机选择支点来避免。
5. 空间复杂度
-
空间复杂度：O(1)，不考虑递归调用的栈空间。
6. 使用示例
以下是一个使用 nth_element 的示例代码，用于找到一个数组中第 k 小的元素：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> arr = {7, 10, 4, 3, 20, 15};
int k = 3; // 找第 3 小的元素
// 使用 nth_element
std::nth_element(arr.begin(), arr.begin() + k - 1, arr.end());
// 输出第 k 小的元素
std::cout << "第 " << k << " 小的元素是: " << arr[k - 1] << std::endl;
return 0;
}对于上述代码，输出结果为：
第 3 小的元素是: 7
8. 注意事项
-
nth_element不会完全排序整个序列，它只保证第 k 小的元素在正确的位置上。 -
如果需要完全排序，可以使用
std::sort。 -
nth_element的性能优于完全排序（std::sort的时间复杂度为 O(nlogn)），特别是在只需要找到第 k 小的元素时。
9. 自定义比较函数
如果需要根据自定义规则进行排序，可以使用自定义比较函数。例如，以下代码按降序找到第 k 大的元素：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> arr = {7, 10, 4, 3, 20, 15};
int k = 3; // 找第 3 大的元素
// 使用 nth_element 和自定义比较函数
std::nth_element(arr.begin(), arr.begin() + k - 1, arr.end(), std::greater<int>());
// 输出第 k 大的元素
std::cout << "第 " << k << " 大的元素是: " << arr[k - 1] << std::endl;
return 0;
}对于上述代码，输出结果为：
第 3 大的元素是: 10
11. 总结
nth_element 是一个非常高效的算法，适用于以下场景：
需要找到序列中第 k 小或第 k 大的元素。
不需要对整个序列进行完全排序。
需要高效地处理大数据量。
