Основные алгоритмы сортировки:
- Сортировка пузырьком (Bubble Sort): Простой, но неэффективный алгоритм, многократно проходящий по списку, меняя местами соседние элементы, если они в неправильном порядке.
- Сортировка выбором (Selection Sort): Находит наименьший (или наибольший) элемент из неотсортированной части списка и помещает его в начало.
- Сортировка вставками (Insertion Sort): Постепенно строит отсортированный список, вставляя каждый новый элемент в нужное место уже отсортированной части.
- Сортировка слиянием (Merge Sort): Рекурсивный алгоритм, разбивающий список на подсписки, сортирующий их и затем объединяющий обратно.
- Быстрая сортировка (Quick Sort): Алгоритм "разделяй и властвуй", выбирающий опорный элемент (pivot) и перераспределяющий элементы так, чтобы элементы меньше опорного оказались слева, а больше - справа. Затем рекурсивно применяется к подспискам.
- Сортировка Шелла (Shell Sort): Улучшение сортировки вставками, использующее сравнения на больших расстояниях между элементами.
- Пирамидальная сортировка (Heap Sort): Использует структуру данных "куча" (heap) для эффективной сортировки.
Также существуют менее распространенные, но эффективные в определенных случаях алгоритмы, такие как сортировка подсчетом (Counting Sort), поразрядная сортировка (Radix Sort), блочная сортировка (Bucket Sort).
Время выполнения основных алгоритмов (в среднем):
| Алгоритм сортировки | Среднее время выполнения |
|---|
| Сортировка пузырьком | O(n²) |
| Сортировка выбором | O(n²) |
| Сортировка вставками | O(n²) |
| Сортировка слиянием | O(n log n) |
| Быстрая сортировка | O(n log n) |
| Сортировка Шелла | Зависит от шага |
| Пирамидальная сортировка | O(n log n) |
Пример реализации быстрой сортировки на Python:
python