Алгоритм быстрой сортировки (Quicksort)

Один из самых быстрых известных универсальных алгоритмов сортировки. В среднем O(n log(n)) обменов при упорядочивании n элементов.

Общее описание алгоритма:

  1. Выбирается элемент каким-либо образом. Существуют разные способы выбора элемента, но алгоритм работает с любым выбранным элементом. Это может быть самый первый, либо самый последний элемент массива, либо элемент где-то посередине. Этот элемент называется опорным.
  2. Элементы в массиве перемещаются так, что элементы меньше опорного оказываются слева от него, а элементы больше опорного — справа.
  3. К подмассивам слева и справа от опорного применяются первые два шага, если в этих подмассивах больше одного элемента.

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

Реализуем этот алгоритм на Java.

Внимание! Не стоит реализовывать этот алгоритм в реальных проектах. Всегда используйте готовые алгоритмы сортировки коллекций и готовые алгоритмы из класса java.util.Arrays.

Код на Java:

Достоинства алгоритма:

  • Достаточно прост.
  • Довольно быстр.
  • Допускает распараллеливание, так как подмассивы могут сортироваться параллельно.
  • Можно использовать для связанных списков.

Недостатки:

  • При неудачных входных данных может дать до O(n²) по скорости (если исходный массив уже отсортирован)
  • Если делать прямую реализацию с рекурсивными вызовами, то может привести к переполнению стека.
  • Неустойчив, так как меняет порядок равных элементов.

Вас также может заинтересовать сортировка слиянием и сортировка вставками.


Поделиться:
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...

Добавить комментарий

Ваш e-mail не будет опубликован.

*