Какая временная сложность у алгоритма быстрой сортировки (quicksort) в худшем случае?

В худшем случае временная сложность быстрой сортировки составляет O(n²).

Почему это происходит? Худший случай наступает, когда выбранный опорный элемент (pivot) постоянно оказывается минимальным или максимальным в разделяемом подмассиве. Это приводит к максимально несбалансированным разбиениям:

• Одно подмассив содержит n-1 элемент.
• Другое подмассив пуст.

В этом случае глубина рекурсии становится n, и на каждом уровне выполняется работа O(n), что в сумме дает O(n²).

Типичные сценарии худшего случая:

1. Массив уже отсортирован (по возрастанию или убыванию), и в качестве опорного выбирается первый или последний элемент.
2. Все элементы в массиве одинаковые.

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

• Случайный выбор pivot: pivot = array[random(low, high)].
• Медиана из трех: выбор pivot как медианы первого, среднего и последнего элементов.

// Пример реализации быстрой сортировки с выбором случайного опорного элемента
public void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        // Выбор случайного индекса для pivot
        int randomIndex = new Random().Next(low, high + 1);
        Swap(arr, randomIndex, high); // Перемещаем случайный элемент в конец

        int pi = Partition(arr, low, high);
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}

При таких оптимизациях средняя и ожидаемая сложность составляет O(n log n), что делает алгоритм эффективным на практике.