std::sort() 算法

自 C++20 起

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

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

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

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

自 C++17 起

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

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

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

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

C++17 之前

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

// (3)
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

将范围 [first; last) 中的元素按升序排序。

如果对于指向序列的任何迭代器it和任何非负整数n（使得it + n是指向序列元素的有效迭代器），comp(*(it + n), *it)（或*(it + n) < *it）计算结果为false，则序列相对于比较器comp是已排序的。

重要

不保证相等元素的顺序得到保留。

• (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	要排序的元素范围。
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

返回值

(无)

复杂度

无论实现如何，保证 O(N * log(N)) 次比较，其中 N 是 std::distance(first, last)。

异常

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

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

可能的实现

参见来自libstdc++和libc++的实现。

备注

在LWG713之前，复杂性要求允许sort()仅使用快速排序实现，这在最坏情况下可能需要O(N²)次比较。

内省排序可以处理所有情况，具有 O(N * log(N)) 次比较（在平均情况下不会产生额外开销），因此通常用于实现 sort()。

libc++ 直到LLVM 14才实现纠正后的时间复杂度要求。

示例

Main.cpp

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

int main()
{
    std::array<int, 10> s {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

    auto print = [&s](std::string_view const rem)
    {
        for (auto a : s)
            std::cout << a << ' ';
        std::cout << ": " << rem << '\n';
    };

    std::sort(s.begin(), s.end());
    print("sorted with the default operator<");

    std::sort(s.begin(), s.end(), std::greater<int>());
    print("sorted with the standard library compare function object");

    struct
    {
        bool operator()(int a, int b) const { return a < b; }
    }
    customLess;

    std::sort(s.begin(), s.end(), customLess);
    print("sorted with a custom function object");

    std::sort(s.begin(), s.end(), [](int a, int b)
                                  {
                                      return a > b;
                                  });
    print("sorted with a lambda expression");
}

输出

0 1 2 3 4 5 6 7 8 9 : sorted with the default operator<
9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object
0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object
9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression