Быстрая сортировка - упорядочение за среднее время О(n log n).

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы (Алгоритм, приведённый ниже, неверен: если в массиве оказалось два элемента, равных опорному и индексы l и r достигли их одновременно, то шаг 2.6 не изменяет массива при обмене этих элементов и алгоритм оказывается в вечном цикле. В англоязычной версии статьи приведён правильно действующий псевдо-код):

Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

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

Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.

Вычисляется индекс опорного элемента m.

Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.

Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.

Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута обязательно и обработка гарантированно завершится.

public static void qSort(int [] A, int low, int high) {

int i = low;

int j = high;

int x = A[(low+high)/2]; // x - опорный элемент посредине между low и high

do {

while (A[i] < x) ++i; // поиск элемента для переноса в старшую часть

while (A[j] > x) --j; // поиск элемента для переноса в младшую часть

if (i <= j){

// обмен элементов местами:

int temp = A[i];

A[i] = A[j];

A[j] = temp;

// переход к следующим элементам:

i++; j--;

}

} while (i < j);

if (low < j) qSort(A, low, j);

if (i < high) qSort(A, i, high);

}

Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C_N = 2C_N/2+N, что в явном выражении дает примерно N lg N сравнений. Это дало бы наименьшее время сортировки.

Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n lg n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2C_N/2 покрывает расходы по сортировке двух полученных подмассивов; N — это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно C_N = N lg N.

Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Худший случай даёт O(n ²) обменов. Но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.