3622
правки
Изменения
м
<wikitex>{{в разработке}}''Сортировкой'' называется процесс упорядочивания множества объектов по какому-либо признаку. Обычно таким признаком служит лексикографический номер. Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке, нежели чем в массиве, сортировка слиянием потребует $O(n^2)$ времени и $O(1)$ памяти против $O(n \log n)$ и $O(n)$ с использованием массива; а вот сортировка пузырьком не изменится. == Классификация сортировок == Будем рассматривать сортировки массива из $n$ элементов множества $A$, причем на $A$ должно быть выполнено [[Бинарное отношение|отношение эквивалентности]].=== Время работы. === Эта классификация является самой важной. Оценивают худшее время алгоритма, среднее и лучшее.У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$. === Память === Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$. === #Стабильность === ''Стабильной сортировкой'' называется сортировка, не меняющая порядка объектов с одинаковыми ключами. === Количество обменов === Важный параметр, когда объекты имеют большой размер. В таком случае при большом кол-ве обменов время алгоритма заметно увеличивается. == Сравнение сортировок == {|class="wikitable"|+!width="15%"|Название !!width="8%"| Лучшее время !!width="8%"| Среднее !!width="8%"| Худшее !!width="8%"| Память !! width="8%"|Стабильность !! width="10%| Обмены (в среднем) !! "width="35%"| Описание|- align = "center"|[[Сортировка пузырьком| Сортировка пузырьком <br>(Bubble Sort)]]|$O(n)$|$O(n^2)$|$O(n^2)$|$O(1)$|Да|$O(n^2)$|Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.|- align = "center"|[[Сортировка вставками| Сортировка вставками <br>(Insertion Sort)]]|$O(n)$|$O(n^2)$|$O(n^2)$|$O(1)$|Да|$O(n^2)$|На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.|- align = "center"|[[Сортировка выбором| Сортировка выбором<br> (Selection Sort)]]|$O(n^2)$|$O(n^2)$|$O(n^2)$|$O(1)$|Нет|$O(n)$|На каждом $i$-ом шаге алгоритма находим $i$-ый минимальный элемент и меняем его местами с $i$-ым элементом в массиве.|- align = "center"|[[Быстрая сортировка|Быстрая сортировка<br> (Quick Sort)]]|$O(n \log n)$|$O(n \log n)$|$O(n^2)$<br>(маловероятно)|$O(\log n)$<br>(стек вызовов)|Нет|$O(n \log n)$|Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного и в сортировке полученных частей.|- align = "center"|[[Сортировка слиянием|Сортировка слиянием <br>(Merge Sort)]]|$O(n \log n)$|$O(n \log n)$|$O(n \log n)$|$O(n)$ (обычная реализация)<br>$O(\log n)$<br> ([[Cортировка слиянием с использованием O(1) дополнительной памяти|модифицированная реализация]])|Да|$O(n \log n)$|Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.|- align = "center"|[[Сортировка кучей|Пирамидальная сортировка <br>(Heap Sort)]]|$O(n \log n)$|$O(n \log n)$|$O(n \log n)$|$O(1)$|Нет|$O(n \log n)$|Строим из массива кучу, по очереди извлекаем минимум кучи.|- align = "center"|[[Дерево поиска, наивная реализация|Сортировка с помощью бинарного дерева <br>(Tree Sort)]]|$O(n)$|$O(n \log n)$|$O(n \log n)$|$O(n)$|Да|$O(n)$|Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания.|- align = "center"|[[Карманная сортировка|Карманная сортировка <br>(Bucked Sort)]]|$O(n)$|$O(n \log_k n)$|$O(n^2)$|$O(n)$|Да| -|распихиваем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.|- align = "center"|[[Цифровая сортировка|Цифровая сортировка <br>(Radix Sort)]]|$O(n \lg n)$|$O(n \lg n)$|$O(n \lg n)$|$O(n)$|Да| -|сортировка, аналогичная карманной. карманы в данном случае - цифры от 0 до 9.|- align = "center"|[[Сортировка подсчетом|Сортировка подсчетом <br>(Counting Sort)]]|$O(n)$|$O(n + k)$|$O(k)$|$O(n + k)$|Да|$O(n + k)$|Сортировка объектов, ключи которых входят в заранее известный диапазон целых чисел. $k$ - длина диапазона.|- align = "center"|[[Сортировка Хэна (или Хана?)|Сортировка Хэна <br>(Han's Sort)]]|$O(n \log \log n)$|$O(n \log \log n)$|$O(n \log \log n)$|$O(n)$|Да|$O(n \log \log n)$|Упоротая сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона.|} == Ссылки == [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8| Википедия срывает покровы]</wikitex>[[Категория: Дискретная математика и алгоритмы]]перенаправление [[Категория: Сортировки]]
Перенаправление на Сортировки
