0Pricing
C++ Academy · Урок

Сортировка и разбиение: sort, stable_partition

Сортируйте и разбивайте контейнеры с помощью std::sort и std::stable_partition.

«Сортировка и разбиение: sort, stable_partition» — бесплатный урок C++ Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения 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

Пользовательский компаратор

Передайте компаратор — лямбда-выражение или функтор, — чтобы сортировать по другим критериям.

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

То же, что и 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, когда важен порядок равных элементов, std::partial_sort для выбора k лучших элементов, std::nth_element для выбора элемента и std::partition/std::stable_partition для группировки.

Часто задаваемые вопросы

Урок «Сортировка и разбиение: sort, stable_partition» бесплатный?

Да — полный текст урока «Сортировка и разбиение: sort, stable_partition» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C++ Academy, подпишись на CoddyKit PRO. Курс C++ Academy содержит 4 уроков всего.

Чему я научусь в уроке «Сортировка и разбиение: sort, stable_partition»?

Сортируйте и разбивайте контейнеры с помощью std::sort и std::stable_partition. Ты практикуешь C++ Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C++ Academy?

Предыдущий опыт не требуется. C++ Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Сортировка и разбиение: sort, stable_partition»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C++ Academy?

Да. Каждый урок C++ Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Алгоритмы без изменения: find, count, all_of
  2. Изменяющие алгоритмы: transform, copy_if, replace
  3. Сортировка и разбиение: sort, stable_partition
  4. Числовые алгоритмы: accumulate, reduce, transform_reduce
← Назад к C++ Academy