Ответ
Худший случай — O(n²). Это происходит при постоянном выборе опорного элемента (pivot), который делит массив на подмассивы размером n-1 и 0 (несбалансированное разбиение).
Типичные сценарии:
- Уже отсортированный (или обратно отсортированный) массив, если pivot всегда выбирается как первый (или последний) элемент.
- Массив, где все элементы равны.
Пример худшего случая:
int[] arr = {1, 2, 3, 4, 5}; // Отсортированный массив
// При выборе первого элемента как pivot:
// 1-е разбиение: [] + [2,3,4,5]
// 2-е разбиение: [] + [3,4,5]
// ... итого ~ n²/2 операций.Меры предотвращения:
- Randomized QuickSort: Выбор случайного pivot.
- Медиана трёх: Выбор pivot как медианы первого, среднего и последнего элементов.
- Introsort: Гибридный алгоритм, переключающийся на Heapsort при глубокой рекурсии.