Алгоритмы сортировки

Алгоритм «разделяй и властвуй» с опорным элементом (pivot). Средняя сложность O(n log n), худшая O(n²). Изобретён Хоаром (1960). Partition перегруппирует элементы: меньше pivot слева, больше справа.

Рекурсивное деление массива пополам до 1 элемента, затем слияние отсортированных половин. Гарантированная сложность O(n log n). Стабильная. Требует O(n) дополнительной памяти. Фон Нейман, 1945.

Построение кучи (heap) из массива, затем извлечение максимума в конец. Сложность O(n log n) всегда. На месте (in-place), нестабильная. Введена Уильямсом (1964). Используется в priority queue.

Подсчёт частоты каждого значения в массиве, затем восстановление. Линейная сложность O(n + k), где k — диапазон значений. Стабильная. Применима для целых чисел в ограниченном диапазоне.

Построение отсортированной части массива слева направо. Каждый элемент вставляется на своё место. Сложность O(n²), но эффективна для малых массивов (< 10). Адаптивная: O(n) на почти отсортированных.

Поиск минимума в неотсортированной части, обмен с первым элементом. Повтор для остальных. Сложность O(n²) всегда. Минимальное число обменов (n-1). Нестабильная, проста для понимания.

Попарное сравнение соседних элементов, «всплытие» максимума вправо. Сложность O(n²), неэффективна для больших данных. Стабильная. Адаптивная с ранним выходом. Учебная цель.

Комбинация MergeSort и InsertionSort, используется в Python и Java. Делит массив на runs, сортирует вставками, сливает. Стабильная, O(n log n), адаптивная к частично отсортированным данным. Тим Питерс, 2002.

Алгоритм "разделяй и властвуй" (1960, Тони Хоар). Выбирает опорный элемент, разбивает массив на меньшие/большие. Средняя сложность O(n log n), худшая O(n²). Самый быстрый на практике.

Стабильный алгоритм "разделяй и властвуй" (1945, Джон фон Нейман). Делит массив пополам, сортирует рекурсивно, сливает. Гарантированно O(n log n), требует O(n) памяти.

Использует структуру двоичной кучи (1964, Дж. Уильямс). Строит max-heap, извлекает максимумы. O(n log n) гарантированно, in-place, но не стабильная. Используется в introsort.

Простейший алгоритм: сравнивает соседние элементы, меняет местами. O(n²) всегда. Учебный пример неэффективного алгоритма, на практике не используется для больших данных.

Вставляет каждый элемент в отсортированную часть. O(n²) в среднем, но O(n) для почти отсортированных данных. Стабильная, in-place. Эффективна для малых массивов (< 50 элементов).