Алгоритмы сортировки в основном используются для сортировки массива.
Почему важны алгоритмы сортировки
Поскольку сортировка часто может уменьшить сложность проблемы, это важный алгоритм в информатике. Эти алгоритмы имеют прямое применение в алгоритмах поиска, алгоритмах баз данных, методах разделяй и властвуй, алгоритмах структуры данных и многом другом.
Классификация алгоритма сортировки
Алгоритмы сортировки можно классифицировать по следующим параметрам:
- На основе количества перестановок или инверсий. Это количество раз, когда алгоритм меняет местами элементы для сортировки входных данных.
Selection Sort
требует минимального количества свопов. - Основано на количестве сравнений. Это число раз, которое алгоритм сравнивает элементы для сортировки входных данных. Используя нотацию Big-O, приведенные выше примеры алгоритмов сортировки требуют не менее
O(nlogn)
сравнений в лучшем случае иO(n^2)
сравнений в худшем случае для большинства выходных данных. - На основе рекурсии или нерекурсии Некоторые алгоритмы сортировки, такие как
Quick Sort
, используют рекурсивные методы для сортировки входных данных. Другие алгоритмы сортировки, такие какSelection Sort
илиInsertion Sort
, используют нерекурсивные методы. Наконец, некоторые алгоритмы сортировки, такие какMerge Sort
, используют как рекурсивные, так и нерекурсивные методы для сортировки ввода. - Алгоритмы сортировки на основе стабильности называются
stable
, если алгоритм поддерживает относительный порядок элементов с одинаковыми ключами. Другими словами, два эквивалентных элемента остаются в том же порядке в отсортированном выводе, что и во входных данных. Insertion sort
,Merge Sort
иBubble Sort
стабильныHeap Sort
иQuick Sort
нестабильны- Алгоритмы сортировки, основанные на требованиях к дополнительному пространству, называются
in place
, если они требуют постоянногоO(1)
дополнительного пространства для сортировки. Insertion sort
иQuick-sort
являются сортировкойin place
, так как мы перемещаем элементы вокруг оси и фактически не используем отдельный массив, чего НЕТ в случае сортировки слиянием, где размер ввода должен быть выделен заранее для хранения вывода во время сортировки.Merge Sort
является примером сортировкиout place
, поскольку для ее операций требуется дополнительное пространство памяти.
1. ПУЗЫРЬКОВАЯ СОРТИРОВКА
2. СОРТИРОВКА ВЫБОРОМ
3. СОРТИРОВКА ВСТАВКОЙ
4. БЫСТРАЯ СОРТИРОВКА
5. СОРТИРОВКА СЛИЯНИЕМ
Это основной алгоритм сортировки, но если вы хотите попробовать больше, вы должны узнать о сортировке подсчетом, сортировке по основанию, сортировке сегментами и т. д.