Ответ
Существует множество алгоритмов сортировки, различающихся по эффективности, требованиям к памяти и стабильности. Вот основные из них:
-
Сортировка пузырьком (Bubble Sort)
- Принцип: Многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они стоят в неверном порядке. Самые "тяжелые" элементы "всплывают" в конец.
- Сложность: O(n²)
- Особенности: Прост для понимания, но крайне неэффективен на больших данных.
-
Сортировка выбором (Selection Sort)
- Принцип: Находит минимальный элемент в неотсортированной части массива и ставит его в начало.
- Сложность: O(n²)
- Особенности: Нестабильный, но делает минимальное количество обменов.
-
Быстрая сортировка (Quick Sort)
- Принцип: Использует подход "разделяй и властвуй". Выбирается опорный элемент (pivot), и массив делится на две части: элементы меньше опорного и элементы больше опорного. Процесс рекурсивно повторяется для каждой части.
- Сложность: В среднем O(n log n), в худшем случае O(n²).
- Особенности: Один из самых быстрых алгоритмов на практике, но нестабильный.
-
Сортировка слиянием (Merge Sort)
- Принцип: Также использует "разделяй и властвуй". Массив рекурсивно делится пополам до тех пор, пока не останутся единичные элементы, а затем отсортированные части сливаются обратно.
- Сложность: O(n log n) в любом случае.
- Особенности: Стабильный, но требует дополнительной памяти O(n) для слияния.
-
Timsort
- Принцип: Гибридный алгоритм, сочетающий сортировку слиянием и сортировку вставками. Эффективно работает на частично отсортированных данных.
- Сложность: O(n log n) в худшем случае, O(n) в лучшем.
- Особенности: Это стандартный алгоритм сортировки в Python (
list.sort(),sorted()).
| Алгоритм | Средняя сложность | Худшая сложность | Доп. память | Стабильность |
|---|---|---|---|---|
| Пузырьковая | O(n²) | O(n²) | O(1) | Да |
| Выбором | O(n²) | O(n²) | O(1) | Нет |
| Быстрая | O(n log n) | O(n²) | O(log n) | Нет |
| Слиянием | O(n log n) | O(n log n) | O(n) | Да |
| Timsort | O(n log n) | O(n log n) | O(n) | Да |