std::partial_sort() 算法

自 C++20 起

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

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

// (3)
template< class ExecutionPolicy, class RandomIt >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last );

// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last, Compare comp );

自 C++17 起

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

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

// (3)
template< class ExecutionPolicy, class RandomIt >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last );

// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last, Compare comp );

C++17 之前

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

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

重新排列元素，使范围 [first; middle) 包含范围 [first; last) 中已排序的 middle - first 个最小元素。

注意

不保证保留相同元素的顺序。范围 [middle; last) 中剩余元素的顺序未指定。

• (1) 元素使用 operator< 进行比较。

• (2) 元素使用给定的二元比较函数 comp 进行比较。

• (3, 4) 与 (1) 和 (2) 相同，但根据策略执行。

  重载决议

  这些重载仅在 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 起）

参数

first last	要部分排序的元素范围。
middle	定义要排序范围的末尾迭代器。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
cmp	比较函数对象（即满足 Compare 要求的对象）。比较函数的签名应等同于以下内容： bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受所有（可能是 const）Type 和 Type2 类型的值，无论值类别如何（因此不允许 Type1&，除非对于 Type1 移动等同于复制，否则也不允许 Type1 （自 C++11 起）） `Type1` 和 `Type2` 类型必须是 `RandomIt` 类型的对象可以隐式转换为它们两者的类型。

类型要求

RandomIt	ValueSwappable LegacyRandomAccessIterator
解引用RandomIt的类型	MoveAssignable MoveConstructible
Compare	Compare

返回值

(无)

复杂度

大约 (last - first) * log(middle - first) 次 comp 调用。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

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

可能的实现

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(2)

namespace impl {

template<typename RandomIt, typename Compare>
// constexpr
void sift_down(RandomIt first, RandomIt last, const Compare& comp)
{
    // sift down element at 'first'
    const auto length = static_cast<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
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);
}

备注

使用的算法通常是堆选择（heap select）来选择最小元素，以及堆排序（heap sort）以升序对堆中选定的元素进行排序。

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

选择后使用堆排序来排序 [first; middle) 中选定的元素（参见std::sort_heap）。

std::partial_sort 算法旨在用于少量常数个 [first; middle) 选定元素。

示例

Main.cpp

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

void print(auto const& 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
        ^----------