7 наиболее часто используемых алгоритмов сортировки

Когда мы пишем стратегию, в программе неизбежно появляется ситуация, когда требуется сортировка данных, так как же мы можем создать научную программу с минимальными затратами на систему (время, системные ресурсы)?

• ### 1. Быстрая сортировка

Описание: Быстрое сортирование - это алгоритм сортировки, разработанный Тони Холлом. В средних условиях для сортировки n объектов требуется О (n log n) сравниваний. В худших условиях требуется О (n 2) сравниваний, но это нечасто встречается. Что делать? Выберите один элемент из ряда, называемый базовым элементом (пивотом), Пересортировать массив так, чтобы все элементы, меньшие, чем базовая величина, находились впереди базы, а все элементы, большие, чем базовая величина, находились позади базы. После выхода из этого раздела, эта база находится в среднем месте массива. Это называется операцией разделения. Рекурсивное (recursive) подсоединение подмножеств, меньших, чем элементы базовой величины, и подмножеств, больших, чем элементы базовой величины. Эффект сортировки:

• ### 2. Приведение и сортировка

Описание: Merge sort - эффективный алгоритм сортировки, основанный на операции по объединению. Этот алгоритм является типичным примером применения метода деления и завоевания. Что делать? Заявление на пространство размером суммы двух уже сортированных последовательностей, которое используется для хранения объединенных последовательностей Установка двух указателей, начальные позиции которых являются начальными позициями двух уже сортированных последовательностей Сравнение элементов, на которые указывают два указателя, выбор относительно небольшого элемента, помещенного в объединительное пространство, и перемещение указателя в следующее место Повторите шаг 3 до тех пор, пока один из указателей не достигнет конца последовательности Все элементы, оставшиеся в другой последовательности, копируются непосредственно в конец последовательности объединения Эффект сортировки:

• ### 3. Сортировка кучи

Описание: Heapsort - алгоритм сортировки, разработанный с использованием такой структуры данных, как куча. Куча представляет собой структуру, приближающуюся к полному бинарному дереву, и одновременно удовлетворяет свойствам кучи: ключевое значение или индекс подключенного узла всегда меньше (или больше) его родительского узла. Что делать? (Это сложнее, проверьте сами) Эффект сортировки:

• ### 4. Выбор последовательности

Описание: Selection sort - простой и интуитивно понятный алгоритм сортировки. Он работает следующим образом: сначала найдите наименьший элемент в несортированной последовательности, поместите его в начальное место, затем продолжайте искать наименьший элемент из оставшихся несортированных элементов и поместите его в конец последовательности. Эффект сортировки:

• ### Сортировка пузырьков

Описание: Bubble Sort - это простой алгоритм сортировки, в котором элементы, которые уже были сортированы, пересекаются, сравниваются, а если они не в правильном порядке, то их заменяют друг на друга. Работа по посещению ряда выполняется до тех пор, пока не будет больше необходимости в обмене, то есть, когда совокупность уже сортирована. Что делать? Сравните соседние элементы. Если первый больше второго, то обменивайте их обоих. Сделайте то же самое для каждой пары соседних элементов, начиная с первой пары и заканчивая последней. На этом этапе последняя пара элементов должна быть наибольшей. Повторите все вышеперечисленные шаги для всех элементов, кроме последнего. Продолжайте повторять вышеперечисленные шаги с каждым понемногу уменьшающимся числом элементов, пока ни одна пара чисел не будет нуждаться в сравнении. Эффект сортировки:

• ### Вставка 6.

Описание: Insertion Sort - алгоритм, описывающий простой и интуитивно понятный алгоритм сортировки. Его принцип работы заключается в том, что, создавая последовательность, он сканирует назад и вперед в сортированной последовательности для несортированных данных, чтобы найти соответствующее место и вставить. Вставка сортировки в реализации обычно использует in-place сортировку, то есть сортировку с дополнительным пространством, которое используется только для O1), поэтому в процессе обратного сканирования требуется повторяющееся постепенное перемещение сортированных элементов назад, чтобы предоставить место для вставки новых элементов. Что делать? Начиная с первого элемента, этот элемент можно считать уже сортированным Выберите элемент и сканируйте вперед-назад в уже отсортированной последовательности элементов Если элемент (ссортированный) больше нового элемента, переместите его в следующее место Повторите шаг 3 до тех пор, пока не найдете элемент, который был сортирован меньше или равен новому элементу Вставить новый элемент в местоположение Повторить шаг 2 Эффект сортировки: (В настоящее время отсутствует)

• ### 7. Серия Хилл

Описание: Сортировка Хилл, также известная как алгоритм декцидно-инкрессионной сортировки, является высокоскоростной и стабильной улучшенной версией сортировки вставки. Сортировка Хилл предлагает улучшенный метод, основанный на следующих двух свойствах вставки: 1, вставка сортировки является эффективной при обработке почти сортированных данных, то есть достигает эффективности линейной сортировки 2, но вставка сортировки, как правило, неэффективны, потому что вставка сортировки может перемещать данные только один>

Я использую в основном методы, которые проще всего, а вы?