nth_element

nth_element 是 C++ 标准库中的一个算法，用于对指定范围的元素进行部分排序。这个算法在给定范围内的元素中，将第 n（由迭代器指定）小的元素移动到正确的位置，并保证该元素左侧的所有元素都不大于它，右侧的所有元素都不小于它。font>

template<class RandomIt>
void nth_element(RandomIt first, RandomIt nth, RandomIt last);

• first：指向范围起始位置的迭代器。
• nth：指向范围内要定位的元素的迭代器。
• last：指向范围结束位置的迭代器。

nth_element 的目的是将范围 [first, last) 中的元素重新排列，使得 nth 处的元素为整个范围中第 nth - first 小的元素。注意，这个函数并不保证元素在 nth 处是完全排序的，而是保证 nth 处的元素是整个范围中的第 nth - first 小的元素。

这个函数的时间复杂度为 O(N)，其中 N 是 last - first 的距离。它的效率在处理大型数据集时比完全排序要高，因为它只关心排在中间位置的元素。

举例说明:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {9, 7, 5, 1, 3, 8, 2, 6, 4};

    std::cout << "原始数组：";
    for (const auto &num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用 nth_element 将第4小的元素移动到正确的位置 即下标为3的元素
    std::nth_element(numbers.begin(), numbers.begin() + 3, numbers.end());

    std::cout << "经过 nth_element 后的数组：";
    for (const auto &num : numbers) {
        std::cout << num << " "; // 1 2 3 4 5 8 7 6 9 
    }
    std::cout << std::endl;

    std::cout << "第4小的元素是：" << numbers[3] << std::endl; // 4

    return 0;
}

这个函数还可以自己指定谓词, 即排序规则, 用来找第n大的元素(逆向思维也可以)

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = { 9, 7, 5, 1, 3, 8, 2, 6, 4 };
    int n = 4;  // 找第4大的元素

    std::cout << "原始数组：";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用 nth_element 找第n大的元素
    std::nth_element(numbers.begin(), numbers.begin() + n - 1, numbers.end(), std::greater<int>());
    // 排序后数组
    for (const auto& num : numbers) {
        std::cout << num << " "; // 9 8 7 6 5 4 3 2 1
    }
    std::cout << std::endl;

    std::cout << "第" << n << "大的元素是：" << numbers[n - 1] << std::endl; // 6

    return 0;
}