C++中std::partial_sort的使用小结

目录

• 1. 语法
• 2. 基本用法
• 3. 使用自定义比较编程客栈函数
• 4. 与 std::sort 和 std::nth_element 的比较
• 5. 适用场景

std::partial_sort 是 C++ 标准库中的一个算法，它可以对容器中的一部分元素进行排序，使得前 N 个元素按顺序排列，而不保证剩余部分有序。它的时间复杂度为 O(N log N + (M-N))，其中 M 是整个范围的android大小，N 是要排序的元素数量。

1. 语法

#include <algorithm>

template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );

template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );

• first：要排序的范围的起始迭代器。
• middle：指定排序后的前 N 个元素的终点，即 first +编程 N。
• last：排序范围的结束迭代器。
• comp（可选）：自定义比较函数。

2. 基本用法

#include <IOStream>
#include <vector>
#include <algorithm>

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

    // 仅对前 5 个元素排序
    std::partial_sort(vec.begin(), vec.begin() + 5, vec.end());

    // 输出前 5 个排序后的元素
    std::cout << "前 5 个最小的元素: ";
    for (int i = 0js; i < 5; ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << "\n";

    // 输出整个数组
    std::cout << "整个数组: ";
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    return 0;
}

输出

前 5 个最小的元素: 1 2 3 4 5 

整个数组: 1 2 3 4 5 9 8 7 6 

注意：前 5 个元素是有序的，但整个数组仍然是部分无序的。

3. 使用自定义比较函数

可以使用 std::greater<int>() 进行降序排序：

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

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

    // 获取前 5 个最大的元素（降序）
    std::partial_sort(vec.begin(), vec.begin() + 5, vec.end(), std::greater<int>());

    // 输出前 5 个排序后的元素
    std::cout << "前 5 个最大的元素: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << "\n";

    return 0;
}

输出

前 5 个最大的元素: 9 8 7 6 5 

4. 与 std::sort 和 std::nth_element 的比较

5. 适用场景

• 求前 K 个最小/最大值
• 数据流处理（流式计算）
• Top-K 查询
• 快速获取排名前 N 的元素

到此这篇关于C++中std::partial_sort的使用小结的文章就介绍到这了,更多相关C++ std::partial_sort内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！