命名空间
变体
操作

std::sort

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

void sort( ExecutionPolicy&& policy,

           RandomIt first, RandomIt last );
(2) (自 C++17 起)
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );
(3) (自 C++20 起为 constexpr)
template< class ExecutionPolicy, class RandomIt, class Compare >

void sort( ExecutionPolicy&& policy,

           RandomIt first, RandomIt last, Compare comp );
(4) (自 C++17 起)

对范围 [firstlast) 中的元素进行非递减排序。不保证相等元素的顺序被保留。

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 - 要排序的元素范围
policy - 要使用的执行策略。有关详细信息,请参阅 执行策略
comp - 比较函数对象(即满足 比较 要求的对象),如果第一个参数小于(即在之前排序)第二个参数,则返回 ​true

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

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

虽然签名不需要包含 const&,但函数必须不能修改传递给它的对象,并且必须能够接受类型为(可能是常量)Type1Type2 的所有值,无论值类别是什么(因此,不允许使用 Type1&,除非 Type1 的移动等效于复制(自 C++11 起))。
类型 Type1Type2 必须使得 RandomIt 类型的对象能够被解引用,然后隐式转换为它们中的任何一个。

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

[编辑] 复杂度

假设 Nlast - first

1,2) O(N·log(N)) 次比较,使用 operator<(直到 C++20)std::less{}(自 C++20 起).
3,4) O(N·log(N)) 次比较器 comp 的调用。

[编辑] 异常

带有名为 ExecutionPolicy 的模板参数的重载会报告以下错误

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

[编辑] 可能的实现

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

[编辑] 说明

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

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

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

[编辑] 示例

#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

[编辑] 缺陷报告

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

DR 应用于 已发布的行为 正确行为
LWG 713 C++98 仅在平均情况下需要 O(N·log(N)) 的时间复杂度 在最坏情况下也是必须的

[编辑] 另请参阅

对范围的前 N 个元素进行排序
(函数模板) [编辑]
对元素范围进行排序,同时保留相等元素之间的顺序
(函数模板) [编辑]
将范围排序为升序
(niebloid)[编辑]