命名空间
变体
操作

std::partial_sort

来自 cppreference.com
< cpp‎ | algorithm
 
C++
 
算法库
受约束的算法和范围上的算法 (C++20)
受约束的算法，例如 ranges::copy, ranges::sort, ...
执行策略 (C++17)
排序和相关操作
分区操作
排序操作
二分搜索操作
(在分区范围上)
集合操作（在排序范围上）
合并操作（在排序范围上）
堆操作
最小/最大操作
(C++11)
(C++17)
字典序比较操作
(C++20)
排列操作
C 库
数值操作
对未初始化内存的操作
 
在头文件 <algorithm> 中定义
template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );
 (1) (从 C++20 开始为 constexpr)
template< class ExecutionPolicy, class RandomIt >

void partial_sort( ExecutionPolicy&& policy,

                   RandomIt first, RandomIt middle, RandomIt last );
 (2) (从 C++17 开始)
template< class RandomIt, class Compare >

void partial_sort( RandomIt first, RandomIt middle, RandomIt last,

                   Compare comp );
 (3) (从 C++20 开始为 constexpr)
template< class ExecutionPolicy, class RandomIt, class Compare >

void partial_sort( ExecutionPolicy&& policy,
                   RandomIt first, RandomIt middle, RandomIt last,

                   Compare comp );
 (4) (从 C++17 开始)

重新排列元素，使得范围 [first, middle) 包含范围 [first, last) 中排名前 middle − first 的元素。

相等元素的顺序无法保证。范围 [middle, last) 中剩余元素的顺序未定义。

1) 元素根据 operator<(直到 C++20)std::less{}(从 C++20 开始) 进行 排序.
3) 元素根据 comp 进行排序。
2,4) 与 (1,3) 相同，但根据 policy 执行。
只有当以下条件满足时，这些重载才参与重载解析

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 为 true.

 (直到 C++20)

std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 为 true.

 (从 C++20 开始)

如果满足以下任何条件，则行为未定义

(直到 C++11)
(从 C++11 开始)

内容

[编辑] 参数

first，last - 定义范围的随机访问迭代器
middle - 定义要排序范围的最后一个元素之后的迭代器的随机访问迭代器
policy - 要使用的执行策略。有关详细信息，请参阅执行策略。
comp - 比较函数对象（即满足Compare要求的对象），如果第一个参数小于（即在顺序上在第二个参数之前），则返回 ​true。

比较函数的签名应等效于以下内容

bool cmp(const Type1& a, const Type2& b);

虽然签名不需要具有const&，但该函数不得修改传递给它的对象，并且必须能够接受类型（可能是 const）Type1 和 Type2 的所有值，无论值类别如何（因此，Type1& 不允许，Type1 也不允许，除非对于 Type1 移动等效于复制(自 C++11 起)）。
类型 Type1 和 Type2 必须使类型 RandomIt 的对象能够被解引用，然后隐式转换为两者。​

类型要求
-
RandomIt 必须满足LegacyRandomAccessIterator的要求。
-
Compare 必须满足Compare的要求。

[编辑] 复杂度

给定 M 作为 middle - first，N 作为 last - first

1,2) 使用operator<(直到 C++20)std::less{}(自 C++20 起)，大约 N·log(M) 次比较。
3,4) 比较器comp大约应用 N·log(M) 次。

[编辑] 异常

具有名为 ExecutionPolicy 的模板参数的重载报告错误如下

  • 如果作为算法的一部分调用的函数的执行抛出异常，并且 ExecutionPolicy 是标准策略之一，则调用std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的。
  • 如果算法未能分配内存，则抛出std::bad_alloc。

[编辑] 可能的实现

另请参阅libstdc++和libc++中的实现。

partial_sort (1) 
template<typename RandomIt>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::value_type VT;
    std::partial_sort(first, middle, last, std::less<VT>());
}
partial_sort (3) 
namespace impl
{
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void sift_down(RandomIt first, RandomIt last, const Compare& comp)
    {
        // sift down element at “first”
        const auto length = static_cast<std::size_t>(last - first);
        std::size_t current = 0;
        std::size_t next = 2;
        while (next < length)
        {
            if (comp(*(first + next), *(first + (next - 1))))
                --next;
            if (!comp(*(first + current), *(first + next)))
                return;
            std::iter_swap(first + current, first + next);
            current = next;
            next = 2 * current + 2;
        }
        --next;
        if (next < length && comp(*(first + current), *(first + next)))
            std::iter_swap(first + current, first + next);
    }
 
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp)
    {
        std::make_heap(first, middle, comp);
        for (auto i = middle; i != last; ++i)
        {
            if (comp(*i, *first))
            {
                std::iter_swap(first, i);
                sift_down(first, middle, comp);
            }
        }
    }
} // namespace impl
 
template<typename RandomIt, typename Compare>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp)
{
    impl::heap_select(first, middle, last, comp);
    std::sort_heap(first, middle, comp);
}

[编辑] 备注

[编辑] 算法

使用的算法通常是堆选择来选择最小的元素，以及堆排序按升序对堆中选择的元素进行排序。

为了选择元素，使用堆（见堆）。例如，对于operator<作为比较函数，最大堆用于选择middle − first个最小的元素。

堆排序在选择之后用于对[first, middle)中选择的元素进行排序（见std::sort_heap）。

[编辑] 预期用途

std::partial_sort 算法旨在用于小的常数数量的[first, middle)中选择的元素。

[编辑] 示例

运行此代码
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
 
void print(const auto& s, int middle)
{
    for (int a : s)
        std::cout << a << ' ';
    std::cout << '\n';
    if (middle > 0)
    {
        while (middle-- > 0)
            std::cout << "--";
        std::cout << '^';
    }
    else if (middle < 0)
    {
        for (auto i = s.size() + middle; --i; std::cout << "  ")
        {}
 
        for (std::cout << '^'; middle++ < 0; std::cout << "--")
        {}
    }
    std::cout << '\n';
};
 
int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print(s, 0);
    std::partial_sort(s.begin(), s.begin() + 3, s.end());
    print(s, 3);
    std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend());
    print(s, -4);
    std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{});
    print(s, -5);
}

可能的输出

5 7 4 2 8 6 1 9 0 3
 
0 1 2 7 8 6 5 9 4 3
------^
4 5 6 7 8 9 3 2 1 0
          ^--------
4 3 2 1 0 5 6 7 8 9
        ^----------

[编辑] 缺陷报告

以下行为更改缺陷报告已追溯应用于以前发布的 C++ 标准。

DR 应用于 已发布的行为 正确的行为
P0896R4 C++98 [first, middle) 和 [middle, last)
不需要是有效的范围		 行为未定义
如果它们中的任何一个是无效的

[编辑] 参见

 部分排序给定的范围，确保它按给定元素进行分区
(函数模板) [编辑]
 复制并部分排序元素范围
(函数模板) [编辑]
 排序元素范围，同时保留相等元素之间的顺序
(函数模板) [编辑]
 按升序排序元素范围
(函数模板) [编辑]
(C++20)
 排序范围的前 N 个元素
(niebloid)[编辑]
取自 "https://cppreference.cn/mwiki/index.php?title=cpp/algorithm/partial_sort&oldid=170564"