{ Быстрая сортировка }
Является улучшенным вариантом алгоритма сортировки с помощью прямого
обмена («Пузырьковая сортировка»), весьма низкой эффективности. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы.
Таким образом, улучшение неэффективного прямого метода сортировки дало один из наиболее эффективных методов.
Алгоритм:
выбрать (опорным) элемент из массива;
перераспределить элементы в массиве так, что элементы меньше опорного помещаются перед ним, а больше или равные после;
применить первые два шага к подмассивам слева и справа от опорных элементов, пока в подмассивах не останется не более одного элемента.
Сложность: Средняя O(n log2 n), Худшая O(n2).
Худший случай.
Если каждое разделение даёт два подмассива размерами 1 и n-1, т.е. при каждом разбиении больший массив будет укорачиваться на 1. Это может произойти, если за опорный будет выбраться либо наименьший, либо наибольший элемент из всех обрабатываемых.
При выборе опорного элемента — первого или последнего в массиве, — такой эффект даст уже отсортированный массив.