Как ответить
Из распространённых алгоритмов сортировки я выделяю три основных типа: квадратичные, быстрые и линейные. Выбор алгоритма упирается в конкретную задачу — размер данных, объём памяти и процент уже отсортированных элементов.
1. Квадратичные O(n²) — для обучения и мелких наборов.
- Пузырьковая сортировка (Bubble Sort): Проходим по массиву, каждый раз «всплывая» максимальный элемент в конец. Время: O(n²) в худшем и среднем, O(n) — если массив уже отсортирован и мы используем оптимизацию с флагом. Память: O(1). На практике почти не применяется — медленная на реальных данных.
- Сортировка вставками (Insertion Sort): Берём следующий элемент и вставляем в уже отсортированную часть массива. Время: O(n²) в худшем, O(n) если массив почти отсортирован — это её преимущество. Память: O(1). Используется в реальных системах, например, в гибридных сортировках вроде Timsort, когда размер подмассива становится маленьким (больше <32 элементов).
- Сортировка выбором (Selection Sort): Находим минимальный элемент и ставим его на текущую позицию. Время всегда O(n²), что бессмысленно. Память: O(1). Встречается только в учебных целях.
2. Быстрые рекурсивные O(n log n) — для общих случаев.
- Быстрая сортировка (Quick Sort): Выбираем опорный элемент (pivot), делим массив на элементы меньше и больше pivot, рекурсивно сортируем части. В среднем O(n log n), в худшем O(n²) — если pivot всегда минимальный/максимальный. Память: O(log n) за счёт рекурсивных вызовов. Основной алгоритм в стандартных библиотеках многих языков, если нужна дополнительная память.
- Сортировка слиянием (Merge Sort): Делим массив пополам, рекурсивно сортируем половинки, затем сливаем. Время всегда O(n log n), память O(n) — из-за дополнительного массива для слияния. Предсказуема, стабильна (сохраняет порядок равных элементов). Часто используется для сортировки связных списков или когда важна гарантия O(n log n).
3. Линейные сортировки — для специальных случаев (опорные значения).
- Поразрядная сортировка (Radix Sort): Сортируем элементы по разрядам чисел (единицы, десятки, сотни). Время O(k*n), где k — количество разрядов, n — количество элементов. Память O(n+k). Работает только для целых чисел или строк фиксированной длины. Реально применяется, когда числа большие, но разрядов мало — например, в высоконагруженных системах обработки логов.
Что я использую в реальных проектах: Для массивов в Python — встроенный list.sort() — это Timsort, гибрид сортировки слиянием и вставками. Для библиотечных классов — стандартный алгоритм из языка. На собеседовании я бы уточнил, какой именно алгоритм нужно реализовать — обычно это быстрая сортировка или слияние.