Всем привет! Подтолкнуло написать меня эту статью мой непосредственный интерес к алгоритмам и решению задач на leetcode, каждый раз, используя стандартную сортировку из STL std::sort, я знал, что ее сложность O(n*log(n)), но как она реализована внутри не доходили руки разобраться, в добавок мне стало интересно, какие есть другие виды сортировок, кроме самых простых, с которыми каждый знакомится в начале своего пути.
Я решил это исправить! И описать все виды сортировок, с которыми мне так или иначе приходилось встречать во время выполнения своих тасков или решению задач на leet.
Начнем с того, что разберемся, какие виды сортировок вообще есть и разобьем их на условные простые/продвинутые/для специальных случаев, а также разберемся, что использует std::sort у себя под капотом.
Начнем!
std::sort — это стандартная функция сортировки, находится в <algorithm>. Она использует комбинацию QuickSort, HeapSort, и InsertionSort для достижения высокой производительности.
-
Алгоритм под капотом:
-
Используется модифицированный introsort (Introspective Sort).
Это гибридный алгоритм, который:
-
Начинает с QuickSort.
-
Если глубина рекурсии становится слишком большой (может указывать на худший случай), переключается на HeapSort.
*Для небольших подмассивов применяется InsertionSort, так как он эффективен для малых объёмов данных.
-
По итогу получаем сложность O(n log n) в среднем случае и гарантированную устойчивость даже для худших случаев.
Идем дальше!
-
Простые алгоритмы (Bubble Sort, Insertion Sort, Selection Sort).
-
Продвинутые алгоритмы (Merge Sort, Quick Sort, Heap Sort).
-
Алгоритмы для специальных случаев (Counting Sort, Radix Sort, Bucket Sort).
Рассмотрим каждый из них и варианты реализации:
1. Простые алгоритмы сортировки
Bubble Sort (Пузырьковая сортировка)
Алгоритм сравнивает соседние элементы и меняет их местами, если правый элемент больше левого. Повторяется до тех пор, пока массив не будет отсортирован.
Сложность: O(n²)
//Сортировка по возрастанию.
template<typename T>
void BubbleSort(std::vector<T>& vec)
{
for (auto it = vec.begin(); it != vec.end(); ++it)
{
for (auto it2 = it ; it2 != vec.end(); ++it2)
{
if (*it2 < *it) {
std::swap(*it, *it2);
}
}
}
}
Меньший элемент перемещается “вверх”, как пузырёк.
Insertion Sort (Сортировка вставками)
Элементы из неотсортированной части массива постепенно вставляются в правильную позицию отсортированной части.
Сложность: O(n²)
template<typename T>
void insertionSort(vector<T>& vec)
{
for (int32_t i = 1; i < vec.size(); ++i)
{
T key = vec[i];
int32_t j = i - 1;
while (j >= 0 && vec[j] > key)
{
vec[j + 1] = vec[j]; --j;
}
vec[j + 1] = key; }
}
Идеально подходит для небольших массивов или почти отсортированных данных.
Selection Sort (Сортировка выбором)
На каждом шаге выбирается минимальный элемент из оставшейся части массива и перемещается в начало.
Сложность: O(n²)
template<typename T>
void selectionSort(vector<T>& vec)
{
for (auto it = vec.begin(); it < vec.end()-1; ++it)
{
auto minIt = it;
for (auto it2 = it + 1; it2 <vec.end(); ++it2)
{
if ((*it2) <(*minIt)) {
minIt = it2;
}
}
swap((*it), *(minIt));
}
}
Простой алгоритм, но неэффективный для больших данных.
Так, на этом этапе я думаю многие вспомнили себя и как они первый раз познакомились с алгоритмами, дальше будут примеры, которые могли вам не встречаться, но они будут асимптотически быстрее и интереснее!
2. Продвинутые алгоритмы сортировки
Merge Sort (Сортировка слиянием)
Идея заключается в том, что вы делите массив на две части, сортирует их рекурсивно и затем сливает в единый отсортированный массив.
Сложность: O(n log n) - уже интереснее, чем O(n²)!
template <typename T>
void merge(vector<T>& vec, uint64_t left, uint64_t mid, uint64_t right) {
vector<T> temp;
uint64_t i = left;
uint64_t j = mid + 1;
while (i <= mid && j <= right) {
if (vec[i] <= vec[j]) {
temp.push_back(vec[i++]);
}
else {
temp.push_back(vec[j++]);
}
}
while (i <= mid) temp.push_back(vec[i++]);
while (j <= right) temp.push_back(vec[j++]);
for (uint32_t k = 0; k < temp.size(); ++k) {
vec[left + k] = temp[k];
}
}
template<typename T>
void mergeSort(vector<T>& vec, uint64_t left, uint64_t right) {
if (left >= right) return;
uint64_t mid = left + (right - left) / 2;
mergeSort<T>(vec, left, mid);
mergeSort<T>(vec, mid + 1, right);
merge<T>(vec, left, mid, right);
}
Quick Sort (Быстрая сортировка)
Выбирается опорный элемент (pivot), элементы меньшие pivot идут влево, больше — вправо. Затем процесс повторяется рекурсивно.
Сложность: Средняя O(n log n), худшая O(n²)
template<typename T>
int64_t partition(vector<T>& vec, int64_t low, int64_t high) {
T pivot = vec[high];
int64_t i = low - 1;
for (int64_t j = low; j < high; ++j) {
if (vec[j] < pivot) {
swap(vec[++i], vec[j]);
}
}
swap(vec[i + 1], vec[high]);
return i + 1;
}
template<typename T>
void quickSort(vector<T>& vec, int64_t low, int64_t high) {
if (low < high) {
int64_t pi = partition(vec, low, high);
quickSort(vec, low, pi - 1);
quickSort(vec, pi + 1, high);
}
}
Heap Sort (Сортировка кучей)
Очень интересный вариант сортировки, потому что строится на heap(кучи), представляющую собой бинарное дерево. Алгоритм сначала строит кучу из массивов, а затем извлекает элементы из кучи по порядку (по возрастанию или убыванию).
Сложность: O(n log n) - при любом случае, так еще и память - O(1) in-place)
Привел описание алгоритма в самом коде
template <typename T>
void heapify(std::vector<T>& vec, int32_t n, int32_t i) {
int32_t largest = i; // Изначально считаем корневой элемент наибольшим
int32_t left = 2 * i + 1; // Левый дочерний узел
int32_t right = 2 * i + 2; // Правый дочерний узел
// Если левый дочерний узел больше корня
if (left < n && vec[left] > vec[largest]) {
largest = left;
}
// Если правый дочерний узел больше корня
if (right < n && vec[right] > vec[largest]) {
largest = right;
}
// Если наибольший элемент — не корень
if (largest != i) {
std::swap(vec[i], vec[largest]);
// Рекурсивно применяем heapify к дочернему узлу
heapify(vec, n, largest);
}
}
template <typename T>
void heapSort(std::vector<T>& vec) {
int32_t n = vec.size();
// Построение кучи (перегруппировка массива)
for (int32_t i = n / 2 - 1; i >= 0; --i) {
heapify(vec, n, i);
}
// Извлечение элементов из кучи
for (int32_t i = n - 1; i > 0; --i) {
// Перемещаем текущий корень (наибольший элемент) в конец массива
std::swap(vec[0], vec[i]);
// Вызываем heapify для уменьшенной кучи
heapify(vec, i, 0);
}
}
3. Алгоритмы для специальных случаев
Почему я назвал их специальные? Потому,что эти алгоритмы подходят для задач с определёнными условиями, например, сортировка целых чисел в ограниченном диапазоне, объектов с ключами фиксированного размера или данных с определённой структурой и другое.
Counting Sort (Сортировка подсчётом)
Counting Sort подходит для сортировки целых чисел в небольшом диапазоне значений. Вместо сравнения элементов используется массив для подсчёта количества вхождений каждого значения.
Сложность: O(n + k), где n — количество элементов, а k — диапазон значений.
Память: O(k).
Особенности:
• Эффективна только для целых чисел в ограниченном диапазоне.
• Не in-place, так как требуется дополнительная память.
template <typename T>
vector<T> countingSort(const vector<T>& vec) {
if (vec.empty()) return {};
// max element
size_t size = vec.size();
T max_elem = *max_element(vec.begin(), vec.end());
// Создаём вектор для подсчёта частоты элементов
vector<size_t> count_vec(max_elem + 1, 0);
for (size_t i = 0; i < size; i++)
{
count_vec[vec[i]]++;
}
// Преобразуем вектор подсчёта в кумулятивную сумму
for (size_t i = 1; i < count_vec.size(); i++)
{
count_vec[i] += count_vec[i - 1];
}
// Формируем результирующий массив
vector<T> result(size);
for (int i = size - 1; i >= 0; i--)
{
result[count_vec[vec[i]] - 1] = vec[i];
count_vec[vec[i]]--;
}
return result;
}
Если входная коллекция будет очень большой, то алгоритм теряет весь смысл, поэтому подчеркну еще раз - Эффективна только для целых чисел в ограниченном диапазоне!
Radix Sort (Поразрядная сортировка)
Radix Sort сортирует числа по разрядам, начиная с младшего. В качестве подалгоритма обычно используется Counting Sort, чтобы обеспечить устойчивость.
Сложность: O(n * d), где n — количество элементов, а d — количество разрядов в числе.
Память: O(n + k), где k — диапазон цифр (обычно 10 для десятичной системы).
Особенности:
• Подходит для чисел (целых или с плавающей точкой) или строк фиксированной длины.
• Требует дополнительных вычислений для обработки отрицательных чисел.
template <typename T>
void countSort(vector<T>& vec, size_t size, T exp) {
vector<T> result(size);
vector<size_t> count(10, 0);
for (size_t i = 0; i < size; i++)
{
count[(static_cast<int>(vec[i] / exp) % 10)]++;
}
// Преобразование count в кумулятивную сумму
for (size_t i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
// Формирование результата, начиная с конца
for (int i = size - 1; i >= 0; i--)
{
int digit = static_cast<int>(vec[i] / exp) % 10;
result[count[digit] - 1] = vec[i];
count[digit]--;
}
// Копирование результата обратно
for (size_t i = 0; i < size; i++)
{
vec[i] = result[i];
}
}
template <typename T>
void radixSort(vector<T>& vec)
{
if (vec.empty()) return;
// max element
T maxElement = *max_element(vec.begin(), vec.end());
// Сортируем по каждому разряду
for (T exp = 1; maxElement / exp > 0; exp *= 10)
{
countSort(vec, vec.size(), exp);
}
}
Bucket Sort (Сортировка корзинами)
Bucket Sort делит элементы на несколько корзин (buckets), сортирует каждую корзину отдельно (обычно с помощью другой сортировки, например, Insertion Sort), а затем объединяет их.
Сложность:
• Лучший случай: O(n) (равномерное распределение элементов по корзинам).
• Худший случай: O(n²) (если все элементы попадают в одну корзину).
Память: O(n + k), где k — количество корзин.
Особенности:
• Эффективен для равномерно распределённых данных.
• Можно используется для чисел с плавающей точкой.
template <typename T>
void bucketSort(vector<T>& arr) {
if (arr.empty()) return;
// Определяем максимальный и минимальный элемент
T minValue = *min_element(arr.begin(), arr.end());
T maxValue = *max_element(arr.begin(), arr.end());
// Вычисляем кол-во корзин
size_t bucketCount = arr.size();
vector<vector<T>> buckets(bucketCount);
// Распределяем элементы по bucket-ам
for (const auto& num : arr) {
size_t bucketIndex = static_cast<size_t>((num - minValue) / (maxValue - minValue + 1) * bucketCount);
buckets[bucketIndex].push_back(num);
}
size_t index = 0;
for (auto& bucket : buckets) {
sort(bucket.begin(), bucket.end()); // Сортируем корзину
for (const auto& num : bucket) {
arr[index++] = num; // Переносим обратно в оригинальный массив
}
}
}
Итог
Внизу приведу таблицу с характеристиками каждого из алгоритмов. Надеюсь, тем, кто не был близко знаком с алгоритмами, стало понятнее и нагляднее, какие варианты сортировок существуют и как они реализуются. Не гонюсь за лучшей реализацией такого, или иного алгоритма, но как по мне, варианты написания, которые я привел, не плохие. Есть еще множество других вариантов сортировок, но как по мне, я привел самые распространенные.
Вот и всё, всем удачи!
Алгоритм |
Устойчивость |
Худший Случай |
В среднем |
Лучший |
Память |
Краткое описание |
Bubble Sort |
Да |
O(n²) |
O(n²) |
O(n) |
O(1) |
Самый просто, но меленный. |
Insertion Sort |
Да |
O(n²) |
O(n²) |
O(n) |
O(1) |
Эффективный для почти отсортированных коллекций. |
Selection Sort |
Нет |
O(n²) |
O(n²) |
O(n²) |
O(1) |
Минимальное число swap-ов. |
Merge Sort |
Да |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
Хорошо подходит для больших массивов |
Quick Sort |
Нет |
O(n²) |
O(n log n) |
O(n log n) |
O(log n) |
Один из самых быстрых на практике |
Heap Sort |
Нет |
O(n log n) |
O(n log n) |
O(n log n) |
O(1) |
Работает на месте, отлично подходит для больших коллекций |
Counting Sort |
Да |
O(n + k) |
O(n + k) |
O(n + k) |
O(k) |
Быстрая сортировка целых с ограниченным диапазоном. Не подходит для float и double |
Radix Sort |
Да |
O(n * d) |
O(n * d) |
O(n * d) |
O(n + k) |
Поразрядная сортировка. Эффективна для чисел или строк фиксированной длины. Нормально работает с большими данными |
Bucket Sort |
Нет |
O(n) |
----- |
O(n²) |
O(n + k) |
Эффективно для равномерно распределенных данных. |
P.S: Устойчивость алгоритма означает, что порядок равных элементов в исходном массиве сохраняется в отсортированном массиве.

Жуков Матвей НИУ МЭИ ИВТИ/Кафедра управления и интеллектуальных технологий
С++ Разработчик в Servicepipe.
Автор: matweu