Основные алгоритмы сортировки, с которыми я знаком:
- Сортировка пузырьком (Bubble Sort). Простая реализация, но низкая эффективность (O(n^2)).
- Сортировка выбором (Selection Sort). Тоже простая, O(n^2), но делает меньше обменов, чем пузырьковая.
- Сортировка вставками (Insertion Sort). Эффективна для почти отсортированных данных или малых наборов (O(n^2) в худшем случае, O(n) в лучшем).
- Сортировка слиянием (Merge Sort). Алгоритм "разделяй и властвуй", стабильный, средняя и худшая сложность O(n log n). Требует дополнительной памяти O(n).
- Быстрая сортировка (Quick Sort). Еще один алгоритм "разделяй и властвуй", обычно самый быстрый на практике (средняя сложность O(n log n)), но в худшем случае O(n^2). Нестабильный.
- Пирамидальная сортировка (Heap Sort). Использует структуру данных "куча". Сложность O(n log n), не требует дополнительной памяти (in-place). Нестабильный.
Python поддерживает несколько встроенных алгоритмов сортировки, которые оптимизированы и используются функцией sorted() и методом списков .sort(). Обычно это Timsort – гибридный алгоритм, сочетающий сортировку слиянием и сортировку вставками, очень эффективный на реальных данных.
Вот пример реализации пузырьковой сортировки:
python
Выбор алгоритма зависит от требований: размера данных, необходимости стабильности, наличия дополнительной памяти и степени предварительной отсортированности данных. В большинстве случаев в Python используются встроенные методы из-за их оптимизации.