C++排序函数汇总（附带实例）

在 C++ 中，有一个常见操作是对 range 进行排序，因为许多标准库函数都需要一个已排序的 range。

C++ 标准库提供了几种对 range 进行排序的通用算法，本节我们将了解这些算法以及如何使用它们。

以下是排序 range 的标准通用算法列表：
1) 使用 std::sort() 对 range 进行排序：

std::vector<int> v{3, 13, 5, 8, 1, 2, 1};

std::sort(v.begin(), v.end());
// v = {1, 1, 2, 3, 5, 8, 13}

std::sort(v.begin(), v.end(), std::greater<>());
// v = {13, 8, 5, 3, 2, 2, 1}

2) 使用 std::stable_sort() 对 range 进行排序，但保持相等元素的顺序不变：

struct Task {
    int priority;
    std::string name;
};

bool operator<(Task const &lhs, Task const &rhs) {
    return lhs.priority < rhs.priority;
}

bool operator>(Task const &lhs, Task const &rhs) {
    return lhs.priority > rhs.priority;
}

std::vector<Task> v{
    { 10, "Task 1"s" }, { 40, "Task 2"s" }, { 25, "Task 3"s" },
    { 10, "Task 4"s" }, { 80, "Task 5"s" }, { 10, "Task 6"s" },
};

std::stable_sort(v.begin(), v.end());
// {{ 10, "Task 1" }, { 10, "Task 4" }, { 10, "Task 6" },
// { 25, "Task 3" }, { 40, "Task 2" }, { 80, "Task 5" }}

std::stable_sort(v.begin(), v.end(), std::greater<>());
// {{ 80, "Task 5" }, { 40, "Task 2" }, { 25, "Task 3" },
// { 10, "Task 1" }, { 10, "Task 4" }, { 10, "Task 6" }}

3) 使用 std::partial_sort() 对 range 的一部分进行排序（其余部分按未指定的顺序排列）：

std::vector<int> v{ 3, 13, 5, 8, 1, 2, 1 };
std::partial_sort(v.begin(), v.begin() + 4, v.end());
// v = {1, 1, 2, 3, 5, 8, ?}

std::partial_sort(v.begin(), v.begin() + 4, v.end(), std::greater<>());
// v = {13, 8, 5, 3, 5, 3, ?}

4) 使用 std::partial_sort_copy() 对 range 的一部分进行排序，它将排序后的元素复制到新的 range，并保持原始 range 不变：

std::vector<int> v{ 3, 13, 5, 8, 1, 2, 1 };
std::vector<int> vc(v.size());

std::partial_sort_copy(v.begin(), v.end(), vc.begin(), vc.end());
// v = {3, 13, 5, 8, 1, 2, 1}
// vc = {1, 1, 2, 3, 5, 8, 13}

std::partial_sort_copy(v.begin(), v.end(), vc.begin(), vc.end(), std::greater<>());
// vc = {13, 8, 5, 3, 5, 3, 2, 1}

5) 使用 std::nth_element() 对 range 进行排序，使第 N 个元素恰好位于它应该在的位置，它之前的元素都较小，它之后的元素都较大，但不需要保证它们也已排序：

std::vector<int> v{ 3, 13, 5, 8, 1, 2, 1 };
std::nth_element(v.begin(), v.begin() + 3, v.end());
// v = {1, 1, 2, 3, 5, 8, 13}
std::nth_element(v.begin(), v.begin() + 3, v.end(), std::greater<>());
// v = {13, 8, 5, 3, 2, 1, 1}

6) 使用 std::is_sorted() 检查 range 是否已排序：

std::vector<int> v { 1, 1, 2, 3, 5, 8, 13 };
auto sorted = std::is_sorted(v.cbegin(), v.cend());
sorted = std::is_sorted(v.cbegin(), v.cend(), std::greater<>());

7) 使用 std::is_sorted_until() 从 range 的开头查找已排序的 range：

std::vector<int> v{ 3, 13, 5, 8, 1, 2, 1 };
auto it = std::is_sorted_until(v.cbegin(), v.cend());
auto length = std::distance(v.cbegin(), it);

以上所有的通用算法都使用随机迭代器作为参数来定义要排序的 range，其中一些也接受输出 range。它们都有重载：

一个重载需要用比较函数或默认 operator< 对元素进行排序；
另一个重载不需要使用比较函数，而是使用 operator< 对元素进行比较。

这些算法的工作方式如下：
1) std::sort() 修改输入 range，使其元素按照默认比较函数或指定的比较函数进行排序，排序的实际算法是一个实现细节。

2) std::stable_sort() 与 std::sort() 类似，但它保证保留相等元素的原始顺序。

3) std::partial_sort() 接受 3 个迭代器参数，它们分别指示 range 中的第一个元素、中间元素和最后一个元素，其中中间元素（middle）可以是任意元素，而不仅仅是位于自然中间位置的元素。结果是一个部分排序的 range，因此原始 range（即 [first,last) 中的前 middle-first 个最小的元素在 [first,middle] 子 range 中找到，其余的元素在 [middle,last] 子 range 中以未指定的顺序找到。

4) std::partial_sort_copy() 不是 std::partial_copy() 的变体，而是 std::sort() 的变体，它通过将元素复制到输出 range 来对 range 进行排序，而不更改它。该算法的参数是输入 range 和输出 range 的开始和结束迭代器：

如果输出 range 的大小 M 大于或等于输入 range 的大小 N，则输入 range 被完全排序并复制到输出 range，输出 range 的前 N 个元素被覆盖，最后的 M-N 个元素保持不变；
如果输出 range 小于输入 range，则只将输入 range 中的前 M 个排序后的元素复制到输出 range（在本例中输出 range 完全被覆盖）。

5) std::nth_element() 基本上是一个选择算法的实现，该算法用于查找 range 中的第 N 个最小元素。该算法接受 3 个迭代器参数，它们分别表示第一个元素、第 N 个元素和最后一个元素，并对 range 进行部分排序，以便在排序后，第 N 个元素将位于它应该在的位置。在修正的 range 内，第 N 个元素之前的 N-1 个元素都小于它，第 N 个元素之后的所有元素都大于它。但是，不能保证这些元素的顺序。

6) std::is_sorted() 检查指定的 range 是否按照指定的比较函数或默认的比较函数进行排序，并返回一个布尔值。

7) std::sorted_until() 使用提供的比较函数或默认 operator<，从指定 range 的开头查找已排序的 range。返回值是一个迭代器，表示已排序子 range 的上界，它也是已排序元素的结束迭代器。

一些标准容器（如 std::list 和 std::forward_list）提供了成员函数 sort()，该函数针对这些容器进行了优化，这些成员函数应该优先于通用标准算法 std::sort()。

C++排序函数汇总（附带实例）

相关文章