名稱空間
變體
操作

std::partial_sort

來自 cppreference.com
< cpp‎ | 演算法
 
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 - 範圍 [first, middle) 將包含已排序的元素
policy - 要使用的 執行策略
comp - 比較函式物件（即滿足 比較 要求的物件），如果第一個引數“小於”（即在第二個引數“之前”排序），則返回 true。

比較函式的簽名應等效於以下內容

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

雖然簽名不需要包含 const&，但函式不得修改傳遞給它的物件，並且必須能夠接受 Type1 和 Type2 型別（可能帶 const）的所有值，無論值類別如何（因此，不允許 Type1&，除非對於 Type1，移動等同於複製，否則也不允許 Type1(自 C++11 起)）。
型別 Type1 和 Type2 必須使得型別為 RandomIt 的物件可以被解引用，然後隱式轉換為這兩種型別。​

型別要求
-
RandomIt 必須滿足 舊版隨機訪問迭代器 的要求。
-
Compare 必須滿足 Compare 的要求。

[編輯] 複雜度

給定 M 為 middle - first，N 為 last - first

1,2) 使用 operator<(直到 C++20)std::less{}(自 C++20 起) 進行大約 N·log(M) 次比較。
3,4) 大約 N·log(M) 次比較器 comp 的應用。

[編輯] 異常

帶有模板引數 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++ 標準。

缺陷報告 應用於 釋出時的行為 正確的行為
P0896R4 C++98 [first, middle) 和 [middle, last)
不需要是有效範圍		 行為未定義
如果其中任何一個無效

[編輯] 另請參閱

 部分排序給定的範圍，確保它被給定的元素劃分
(函式模板) [編輯]
 複製並部分排序一個範圍的元素
(函式模板) [編輯]
 對一個範圍的元素進行排序，同時保留相等元素之間的順序
(函式模板) [編輯]
 將一個範圍按升序排序
(函式模板) [編輯]
(C++20)
 對一個範圍的前 N 個元素進行排序
(演算法函式物件)[編輯]
取自 "https://cppreference.tw/mwiki/index.php?title=cpp/algorithm/partial_sort&oldid=180550"