C++ Academy · 课时

排序与分区：sort、stable_partition

Q: 「排序与分区：sort、stable_partition」课时是免费的吗？

是的 — 「排序与分区：sort、stable_partition」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C++ Academy 课程的其余内容，请升级到 CoddyKit PRO。 C++ Academy 课程共包含 4 节课。

Q: 「排序与分区：sort、stable_partition」这节课中我会学到什么？

使用 std::sort 和 std::stable_partition 对容器排序和分区 你通过在浏览器中直接运行的动手代码来练习 C++ Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 C++ Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C++ Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

Q: 「排序与分区：sort、stable_partition」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 C++ Academy 课中编写并运行代码吗？

能。每节 C++ Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

使用 std::sort 和 std::stable_partition 对容器排序和分区

排序与分区：sort、stable_partition 是 CoddyKit 上的免费 C++ Academy 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C++ Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C++ Academy 课程共包含 4 节课。

std::sort

最常用的排序算法。平均复杂度为 O(N log N)。就地执行。不保证稳定。

#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascending

自定义比较器

传入比较器（lambda 或函数对象），即可按照其他条件排序。

std::sort(v.begin(), v.end(),
    [](int a, int b) { return a > b; });   // descending

对自定义类型排序

提供一个比较特定成员的比较器，或在类型上定义 operator<。

struct Person { std::string name; int age; };
std::vector<Person> people;
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) { return a.age < b.age; });

std::stable_sort

与排序算法相同，但会保留相等元素的相对顺序。速度略慢（通常需要 O(N log^2 N) 的额外内存）。

std::partial_sort

将最小的 k 个元素放在前面并排序。其余元素的顺序未指定。当您只需要前 k 个元素时，它比完整排序更快。

std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// first 3 elements are the smallest, sorted

std::nth_element

进行分区，使 nth 位置上的元素与整个范围完全排序后该位置上的元素相同。前面的所有元素都 ≤ 该元素，后面的所有元素都 ≥ 该元素。平均复杂度为 O(N)。

std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest element

std::is_sorted

检查一个范围是否已经排好序。

if (std::is_sorted(v.begin(), v.end())) {
    std::cout << "already sorted";
}

std::partition

重新排列一个范围，使满足谓词的元素排在前面。返回指向第一个不满足元素的迭代器。不稳定。

std::vector<int> v = {1, 2, 3, 4, 5};
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });
// even numbers come first, then odd

std::stable_partition

类似于 partition，但会保留每个分组内部元素的相对顺序。

按多个键排序

使用一个比较器：先比较主键；如果主键相等，再比较次键。

std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    });

在已排序范围上进行二分查找

排序后，可以使用 std::lower_bound、std::upper_bound 和 std::binary_search 以 O(log N) 的复杂度进行查找。

快速检查

排序后，哪个算法会保留相等元素的相对顺序？

总结

一般排序使用 std::sort；相等元素的顺序很重要时使用 std::stable_sort；获取前 k 个元素时使用 std::partial_sort；选择元素时使用 std::nth_element；分组时使用 std::partition/std::stable_partition。

常见问题解答