C++中std::partial_sort的使用小结-牛翰网

std::partial_sort 是 C++ 标准库中的一个算法，它可以对容器中的一部分元素进行排序，使得前 N 个元素按顺序排列，而不保证剩余部分有序。它的时间复杂度为 O(N log N + (M-N))，其中 M 是整个范围的大小，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 = 0; 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 的比较

算法	作用	复杂度	适用场景
std::sort	全部排序	O(N log N)	需要排序整个序列
std::partial_sort	仅保证前 N 个元素有序	O(N log N + (M-N))	只需要最小/最大 N 个有序元素
std::nth_element	只保证 N 处的元素正确，左侧比它小，右侧比它大	O(M)	只需要找到第 N 小的元素，且不关心其他元素顺序