|
|
| (не показаны 24 промежуточные версии 5 участников) |
| Строка 1: |
Строка 1: |
| − | <wikitex>
| + | #перенаправление [[Сортировки]] |
| − | {{в разработке}}
| |
| − | ''Сортировкой'' называется процесс упорядочивания множества объектов по какому-либо признаку.
| |
| − | | |
| − | Обычно таким признаком служит лексикографический номер.
| |
| − | | |
| − | | |
| − | == Классификация сортировок ==
| |
| − | | |
| − | Будем рассматиривать сортировки массива из $n$ элементов множества $A$,
| |
| − | причем на $A$ должно быть выполнено [[Бинарное отношение|отношение эквивалентности]].
| |
| − | === Время работы. ===
| |
| − | | |
| − | Эта классификация является самой важной. Оценивают худшее время алгоритма, среднее и лучшее.
| |
| − | У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
| |
| − | | |
| − | === Память ===
| |
| − | | |
| − | Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
| |
| − | | |
| − | === Стабильность ===
| |
| − | | |
| − | ''Стабильной сортировкой'' называется сортировка, не меняющая порядка объектов с одинаковыми ключами.
| |
| − | | |
| − | === Количество обменов ===
| |
| − | | |
| − | Важный параметр, когда объекты имеют большой размер.
| |
| − | | |
| − | * Квадратичные. Такие сортировки самые простые в понимании.
| |
| − | ** [[Сортировка пузырьком| Сортировка пузырьком (Bubble Sort)]] - Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
| |
| − | ** [[Сортировка вставками| Сортировка вставками (Insertion Sort)]] - На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
| |
| − | ** [[Сортировка выбором| Сортировка выбором (Selection Sort)]] - На каждом $i$-ом шаге алгоритма находим $i$-ый минимальный элемент и меняем его местами с $i$-ым элементом в массиве.
| |
| − | | |
| − | | |
| − | * $O(n \log n)$. Нормальное время сортировки. Это минимальное время, за которое можно отсортировать массив, [[Теорема о нижней оценке для сортировки сравнениями|используя только сравнения]].
| |
| − | ** [[Быстрая сортировка|Быстрая сортировка (Quick Sort)]]. Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного и в сортировке полученных частей.
| |
| − | ** [[Сортировка слиянием|Сортировка слиянием (Merge Sort)]]. Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.
| |
| − | ** [[Сортировка кучей|Пирамидальная сортировка (Heap Sort)]]. Строим из массива кучу, по очереди извлекаем минимум кучи.
| |
| − | ** [[Карманная сортировка|Карманная сортировка (Bucked Sort)]] - распихиваем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
| |
| − | ** [[Цифровая сортировка|Цифровая сортировка (Radix Sort)]] - сортировка, аналогичная карманной. карманы в данном случае - цифры от 0 до 9.
| |
| − | | |
| − | | |
| − | * Прочие сортировки.
| |
| − | ** [[Сортировка подсчетом]]. Сортировка объектов, ключи которых входят в заранее известный диапазон целых чисел. Время работы - $O(n + k)$, где $k$ - длина диапазона.
| |
| − | ** [[Сортировка Хэна (или Хана?)|Сортировка Хэна]] - упоротая сортировка целых чисел с оценкой $O(n \log \log n)$
| |
| − | | |
| − | | |
| − | === Затраты памяти ===
| |
| − | | |
| − | * $O(1)$. Обычно такие сортировки используют обмены элементов.
| |
| − | ** [[Сортировка пузырьком| Сортировка пузырьком (Bubble Sort)]]
| |
| − | ** [[Сортировка вставками| Сортировка вставками (Insertion Sort)]]
| |
| − | ** [[Сортировка выбором| Сортировка выбором (Selection Sort)]]
| |
| − | ** [[Быстрая сортировка|Быстрая сортировка (Quick Sort)]]
| |
| − | ** [[Сортировка слиянием с использованием О(1) дополнительной памяти|Модифицированная сортировка слиянием]]
| |
| − | ** [[Сортировка кучей|Пирамидальная сортировка (Heap Sort)]]
| |
| − | | |
| − | | |
| − | * $O(n)$
| |
| − | | |
| − | </wikitex>
| |
| − | == Ссылки ==
| |
| − | | |
| − | [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| Википедия срывает покровы]
| |
| − | | |
| − | [[Категория: Дискретная математика и алгоритмы]]
| |
| − | [[Категория: Сортировки]]
| |
