如何在 C++ 标准模板库 (STL) 中排序

使用 C++ 标准库中来自 <algorithm> 的 sort() 函数，将数组或向量就地排序。默认情况下，它按升序对从 first 到（但不包括）last 的半开区间进行排序。传递一个比较器以选择其他排序方式。

使用 sort() 函数在 C++ 中对数组或向量进行排序

std::sort 接受随机访问迭代器，因此它适用于数组和向量。它无法就地重新排列 std::set 或 std::map，因为这些容器不提供随机访问迭代器。这个完整的程序同时对数组和向量进行排序：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    int values[] = {8, 3, 6, 1, 5};
    std::vector<int> scores{14, 7, 22, 9};

    std::sort(std::begin(values), std::end(values));
    std::sort(scores.begin(), scores.end());

    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
    for (int score : scores) std::cout << score << ' ';
    std::cout << '\n';
    return 0;
}

std::begin 和 std::end 提供数组的范围，而向量使用它的 begin() 和 end() 迭代器。这个程序作为未执行的示例提供;在配置的运行环境中观察到其输出之前，输出被省略。这两个调用都会修改原始元素，因此后续代码会以新的顺序看到它们。若只对容器的一部分进行排序，请传递界定该部分的迭代器。

在 C++ 中按降序对数组或向量进行排序

将 std::greater<> 作为第三个参数传递，以将值从最大到最小排序。为比较器包含 <functional>。例如，std::sort(values.begin(), values.end(), std::greater<>{}); 以降序对向量进行排序。比较器改变排序规则，而不改变排序的范围。

使用 partial_sort() 对数组或向量的一部分进行排序

当只有前缀需要排序时，使用 partial_sort(first, middle, last)。它将最小的 middle - first 个元素以排序顺序放在 middle 之前。从 middle 到 last 的元素不保证有任何特定的顺序。例如，std::partial_sort(values.begin(), values.begin() + 3, values.end()); 为前三个位置选择三个最小值。

在 C++ 中使用带有 sort() 的自定义比较器

比较器可以让你按诸如字符串长度之类的键对值进行排序。例如，std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); }); 将较短的字符串放在前面。比较器必须定义一个严格弱序:它必须是一致的，并且不得认为某个项目在它自身之前。在此比较下，长度相等的字符串是等价的，因此它们的相对顺序未指定。使用此示例时，将 <string> 与 <algorithm> 一同包含。

使用 is_sorted() 检查范围是否已排序

当从 first 到（但不包括）last 的范围按默认比较排序时，std::is_sorted(first, last) 返回 true，否则返回 false。它检查范围而不重新排列其元素。在检查自定义排序时，提供用于该排序的相同比较器，如 std::is_sorted(words.begin(), words.end(), compare) 中所示。

排序算法的时间复杂度

对于 std::sort，标准规定在最坏情况下进行 O(N log N) 次比较，其中 N 是范围中的元素数。这描述了工作量如何随范围长度增长;它不承诺任何特定的排序实现。std::partial_sort 在从 N 个元素中选择和排序 K 个元素时使用大约 N log K 次比较，而 std::is_sorted 最多进行 N - 1 次比较。这些界限有助于区分完全对一个范围进行排序、仅对前缀进行排序或检查现有顺序。