---
title: Sorting Algorithms
localeTitle: Алгоритмы сортировки
---
## Алгоритмы сортировки

Алгоритмы сортировки - это набор инструкций, которые принимают массив или список в качестве ввода и упорядочивают элементы в определенном порядке.

Сорта чаще всего относятся к числу или форме алфавитного (называемого лексикографического) порядка и могут быть в порядке возрастания (AZ, 0-9) или нисходящего (ZA, 9-0).

### Почему алгоритмы сортировки важны

Поскольку сортировка часто может уменьшить сложность проблемы, это важный алгоритм в области компьютерных наук. Эти алгоритмы имеют прямые приложения в алгоритмах поиска, алгоритмах баз данных, методах разделения и захвата, алгоритмах структуры данных и многом другом.

### Некоторые общие алгоритмы сортировки

Некоторые из наиболее распространенных алгоритмов сортировки:

*   Выбор Сортировка
*   Сортировка пузырьков
*   Вставка Сортировка
*   Сортировка слиянием
*   Быстрая сортировка
*   Куча сортировки
*   Подсчет сортировки
*   Radix Sort
*   Сортировать по

### Классификация алгоритма сортировки

Алгоритмы сортировки могут быть классифицированы на основе следующих параметров:

1.  Основано на количестве свопов или инверсии Это количество раз, когда алгоритм свопит элементы для сортировки ввода. `Selection Sort` требуется минимальное количество свопов.
    
2.  Основано на количестве сравнений Это число раз, когда алгоритм сравнивает элементы для сортировки ввода. Используя [нотацию Big-O](https://guide.freecodecamp.org/computer-science/notation/big-o-notation/) , приведенные выше примеры алгоритма сортировки требуют, по крайней мере, `O(nlogn)` сравнений в наилучшем случае и сравнения `O(n^2)` в худшем случае для большинства выходов.
    
3.  На основе рекурсии или нерекурсии Некоторые алгоритмы сортировки, такие как `Quick Sort` , используют рекурсивные методы для сортировки ввода. Другие алгоритмы сортировки, такие как `Selection Sort` или `Insertion Sort` , используют нерекурсивные методы. Наконец, некоторые алгоритмы сортировки, такие как `Merge Sort` , используют как рекурсивные, так и нерекурсивные методы для сортировки ввода.
    
4.  Основываясь на стабильности Алгоритмы сортировки считаются `stable` если алгоритм поддерживает относительный порядок элементов с равными ключами. Другими словами, два эквивалентных элемента остаются в том же порядке на отсортированном выходе, что и на входе.
    

*   `Insertion sort` `Merge Sort` `Bubble Sort` стабильны
*   `Heap Sort` и `Quick Sort` нестабильны

1.  Основываясь на дополнительных требованиях к пространству Говорят, что алгоритмы сортировки находятся на `in place` если им требуется постоянное `O(1)` дополнительное пространство для сортировки.

*   `Insertion sort` и `Quick-sort` находятся `in place` своего рода , как мы перемещаем элементы относительно оси поворота и на самом деле не использовать отдельный массив , который не имеет места в сортировках слияния , где размер входа должен быть выделен заранее , чтобы сохранить выход во время Сортировать.
    
*   `Merge Sort` - пример сортировки `out place` поскольку для его операций требуется дополнительное пространство памяти.
    

### Наилучшая возможная временная сложность для любой сортировки на основе сравнения

Любой алгоритм сортировки, основанный на сравнении, должен производить, по меньшей мере, сравнение nLog2n для сортировки входного массива, а сортировка Heapsort и merge - это асимптотически оптимальные сортировки сортировки. Это можно легко доказать, построив диаграмму дерева desicion.