Ответ
Быстрая сортировка (Quick Sort) и сортировка слиянием (Merge Sort) — два эффективных алгоритма, основанных на принципе "разделяй и властвуй", но с ключевыми различиями в подходе и характеристиках.
| Характеристика | Быстрая сортировка (Quick Sort) | Сортировка слиянием (Merge Sort) |
|---|---|---|
| Сложность (средняя) | O(n log n) |
O(n log n) |
| Сложность (худшая) | O(n²) (при неудачном выборе опоры) |
O(n log n) (гарантированно) |
| Память | O(log n) (in-place, под стек рекурсии) |
O(n) (требует доп. массив) |
| Стабильность | Нестабильная | Стабильная |
| Принцип работы | Разделение — сложная часть. Массив делится относительно опорного элемента (pivot). | Слияние — сложная часть. Массив всегда делится пополам, затем отсортированные части сливаются. |
Когда что использовать:
- Quick Sort предпочтительнее, когда важна экономия памяти и высокая средняя производительность (часто быстрее на практике из-за локальности кэша).
- Merge Sort выбирают, когда требуется гарантированное время выполнения
O(n log n)или важна стабильность сортировки (сохранение относительного порядка равных элементов).
Упрощенный пример Quick Sort на Python:
# Примечание: эта реализация наглядна, но не является 'in-place'
# и использует O(n) дополнительной памяти из-за создания новых списков.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
print(quicksort([3, 6, 8, 10, 1, 2, 1]))
# Вывод: [1, 1, 2, 3, 6, 8, 10]