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