В информатике алгоритм сортировки - это алгоритм, который размещает элементы списка в определенном порядке.
Практически любой список, выводимый на компьютере, отсортирован в определенном порядке, а внутри компьютеров есть еще много отсортированных списков, которые пользователь не видит. Было разработано множество умных алгоритмов для эффективного упорядочивания значений. Ниже приведены несколько популярных алгоритмов сортировки:
Пузырьковая сортировка
Пузырьковая сортировка - пузырьковая сортировка, иногда называемая сортировкой по убыванию, представляет собой простой алгоритм сортировки, который многократно проходит по списку для сортировки, сравнивает каждую пару соседних элементов и меняет их местами, если они находятся в неправильный порядок. Прохождение по списку повторяется до тех пор, пока не перестанут использоваться свопы, что указывает на то, что список отсортирован. Алгоритм, который является сравнительной сортировкой, назван в честь того, как более мелкие элементы всплывают вверх по списку. Хотя алгоритм прост, он слишком медленный и непрактичный для большинства проблем даже по сравнению с сортировкой вставкой.
Сложность пузырьковой сортировки
Worst complexity: n² Average complexity: n² Best complexity: n Space complexity: 1 Method: Exchanging Stable: Yes Class: Comparison sort
Сортировка слиянием
Сортировка слиянием. Сортировка слиянием (также обычно обозначается как сортировка слиянием) - это эффективный универсальный алгоритм сортировки, основанный на сравнении. Большинство реализаций производят стабильную сортировку, что означает, что реализация сохраняет порядок ввода одинаковых элементов в отсортированном выходе. Сортировка слиянием - это алгоритм «разделяй и властвуй», изобретенный Джоном фон Нейманом в 1945 году.
Концептуально сортировка слиянием работает следующим образом:
1) Разделите несортированный список на n подсписок, каждый из которых содержит 1 элемент (список из 1 элемента считается отсортированным).
2) Неоднократно объединяйте подсписки для создания новых отсортированных подсписок, пока не останется только 1 подсписок. Это будет отсортированный список.
Сложность сортировки слиянием
Worst complexity: n*log(n) Average complexity: n*log(n) Best complexity: n*log(n) Space complexity: n Method: Merging Stable: Yes
Выбор Сортировка
Выборочная сортировка - выборочная сортировка - это алгоритм сортировки, а именно сортировка на месте сравнения. Алгоритм делит входной список на две части: подсписок уже отсортированных элементов, который создается слева направо в начале (слева) списка, и подсписок элементов, оставшихся для сортировки, которые занимают остальную часть списка. список. Изначально отсортированный подсписок пуст, а несортированный подсписок представляет собой весь входной список. Алгоритм выполняется путем нахождения наименьшего (или наибольшего, в зависимости от порядка сортировки) элемента в несортированном подсписке, обмена (перестановки) его с крайним левым несортированным элементом (помещая его в отсортированном порядке) и перемещения границ подсписка на один элемент вправо. .
Сложность сортировки при выборе
Worst complexity: n² Average complexity: n² Best complexity: n² Space complexity: 1 Method: Selection Stable: No Class: Comparison sort
Сортировка кучи
Heap Sort - heapsort - это алгоритм сортировки на основе сравнения. Heapsort можно рассматривать как улучшенную сортировку выбора: подобно этому алгоритму, он делит входные данные на отсортированную и несортированную области и итеративно сжимает несортированную область, извлекая самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не поиска в линейном времени для поиска максимума. Хотя на практике на большинстве машин она несколько медленнее, чем хорошо реализованная быстрая сортировка, она имеет преимущество в виде более благоприятного времени выполнения O (n log n) в худшем случае.
Алгоритм heapsort включает подготовку списка путем его предварительного преобразования в макс куча. Затем алгоритм несколько раз меняет местами первое значение списка на последнее значение, уменьшая диапазон значений, учитываемых в операции кучи, на единицу и просеивая новое первое значение в его позицию в куче. Это повторяется до тех пор, пока диапазон рассматриваемых значений не станет длиной в одно значение.
Шаги следующие:
1) Вызовите функцию buildMaxHeap () из списка. Также называется heapify (), он создает кучу из списка за O (n) операций.
2) Поменяйте местами первый элемент списка с последним элементом. Уменьшить рассматриваемый диапазон списка на единицу.
3) Вызовите функцию siftDown () в списке, чтобы отсеять новый первый элемент до соответствующего индекса в куче.
4) Переходите к шагу (2), если рассматриваемый диапазон списка не является одним элементом.
Сложность сортировки кучи
Worst complexity: n*log(n) Average complexity: n*log(n) Best complexity: n*log(n) Space complexity: 1 Method: Selection Stable: No
Быстрая сортировка
Быстрая сортировка -Быстрая сортировка (иногда называемая сортировкой с обменом разделами или быстрой сортировкой) - это эффективный алгоритм сортировки, служащий систематическим методом для размещения элементов массива по порядку. При правильной реализации он может быть примерно в два или три раза быстрее, чем его основные конкуренты, сортировка слиянием и сортировка в кучах. Quicksort - это сортировка сравнения, что означает, что она может сортировать элементы любого типа, для которых определено отношение «меньше чем» (формально общий порядок). Quicksort может работать на месте в массиве, требуя небольших дополнительных объемов памяти выполнить сортировку. Математический анализ быстрой сортировки показывает, что в среднем алгоритм выполняет O (n log n) сравнений для сортировки n элементов. В худшем случае он выполняет O (n2) сравнений, хотя такое поведение встречается редко. Quicksort - это алгоритм «разделяй и властвуй». Quicksort сначала делит большой массив на два меньших подмассива: нижние элементы и высокие элементы. Затем Quicksort может рекурсивно сортировать подмассивы.
Шаги следующие:
1) Выберите элемент, называемый опорной точкой, из массива.
2) Измените порядок массива так, чтобы все элементы со значениями меньше, чем точка поворота, располагались перед точкой поворота, а все элементы со значениями больше, чем точка поворота, следовали за ней (равные значения могут быть в любом случае). После этого разбиения стержень находится в окончательном положении. Это называется операцией разделения.
3) Рекурсивно примените вышеуказанные шаги к подмассиву элементов с меньшими значениями и отдельно к подмассиву элементов с большими значениями.
Базовый случай рекурсии - это массивы нулевого или единичного размера, которые никогда не нужно сортировать.
Сложность быстрой сортировки
Worst complexity: n² Average complexity: n*log(n) Best complexity: n*log(n) Method: Partitioning Stable: No Class: Comparison sort
Вставка сортировки
Сортировка вставкой -сортировка вставкой - это простой алгоритм сортировки, который строит окончательный отсортированный массив (или список) по одному элементу за раз. Он намного менее эффективен для больших списков, чем более продвинутые алгоритмы, такие как быстрая сортировка, heapsort или сортировка слиянием. Однако сортировка вставкой дает несколько преимуществ:
1) Простая реализация: Bentley показывает трехстрочную версию C и пятистрочную оптимизированную версию.
2) Эффективен для (довольно) небольших наборов данных, как и другие алгоритмы квадратичной сортировки
3) Более эффективен на практике, чем большинство других простых квадратичных (т.е. O (n2)) алгоритмов, таких как сортировка по выбору или пузырьковая сортировка.
4) Адаптивный, то есть эффективный для наборов данных, которые уже существенно отсортированы: временная сложность составляет O (nk), когда каждый элемент во входных данных находится не более чем на k позиций от его отсортированной позиции.
5) стабильная; т.е. не меняет относительный порядок элементов с одинаковыми ключами
6) на месте; т.е. требуется только постоянное количество O (1) дополнительного пространства памяти
7) Онлайн; то есть может сортировать список по мере его получения.
Когда люди вручную сортируют карты в руке, большинство из них использует метод, похожий на сортировку вставкой.
Наиболее распространенный вариант сортировки вставкой, который работает с массивами, можно описать следующим образом:
1) Предположим, что существует функция с именем Insert, предназначенная для вставки значения в отсортированную последовательность в начале массива. Он работает, начиная с конца последовательности и сдвигая каждый элемент на одну позицию вправо, пока не будет найдено подходящее положение для нового элемента. Функция имеет побочный эффект перезаписи значения, хранящегося сразу после отсортированной последовательности в массиве.
2) Чтобы выполнить сортировку вставкой, начните с самого левого элемента массива и вызовите Insert, чтобы вставить каждый встреченный элемент в его правильную позицию. Упорядоченная последовательность, в которую вставлен элемент, сохраняется в начале массива в уже изученном наборе индексов. Каждая вставка перезаписывает одно значение: вставляемое значение.
Сложность сортировки вставкой
Worst complexity: n² Average complexity: n² Best complexity: n Space complexity: 1 Method: Insertion Stable: Yes Class: Comparison sort
Спасибо, что прочитали эту статью, если вы нашли ее полезной, пожалуйста, оставьте несколько аплодисментов. Я являюсь пользователем YouTube по имени randerson112358, и у меня есть много полезных видео по программированию, информатике и дискретная математика , обязательно зацените!
Также отличная книга для подготовки к собеседованию по кодированию / программированию называется взломать собеседование по кодированию. Это поможет вам ознакомиться с алгоритмами сортировки и решения проблем, поэтому обязательно ознакомьтесь с ним!
