Какие виды сортировок вы знаете и какие у них сложности по времени и памяти?

Существует множество алгоритмов сортировки, вот основные из них с их временной и пространственной сложностью:

• Пузырьковая сортировка (Bubble Sort)

  • Время: O(n²) в худшем и среднем случае
  • Память: O(1) (сортировка на месте)

• Сортировка вставками (Insertion Sort)

  • Время: O(n²) в худшем случае, O(n) в лучшем (почти отсортированный массив)
  • Память: O(1)

• Сортировка выбором (Selection Sort)

  • Время: O(n²) во всех случаях
  • Память: O(1)

• Сортировка слиянием (Merge Sort)

  • Время: O(n log n) во всех случаях
  • Память: O(n) (требует дополнительной памяти для слияния)

• Быстрая сортировка (Quick Sort)

  • Время: O(n log n) в среднем, O(n²) в худшем случае (редко)
  • Память: O(log n) (рекурсивный стек)

• Пирамидальная сортировка (Heap Sort)

  • Время: O(n log n) во всех случаях
  • Память: O(1)

• Тимсорт (Timsort) — гибридная сортировка, используемая в Python и Java

  • Время: O(n log n) в среднем и худшем случае
  • Память: O(n)

Выбор алгоритма зависит от размера данных, требований к памяти и стабильности сортировки (сохраняет ли порядок равных элементов). Например, Merge Sort стабилен, Quick Sort — обычно быстрее, но нестабилен.