Какая средняя алгоритмическая сложность быстрой сортировки?

Question

Средняя сложность быстрой сортировки — O(n log n). В худшем случае (редком) — O(n²). Это один из самых эффективных алгоритмов сортировки на практике.

YeaHub · Accepted Answer

Быстрая сортировка использует стратегию "разделяй и властвуй".1. Как работает:Выбирается опорный элемент (pivot).Массив делится на две части: элементы меньше pivot и больше pivot.Процесс рекурсивно повторяется для каждой части.2. Сложность:Средний случай: O(n log n) — при хорошем выборе pivot.Худший случай: O(n²) — если pivot всегда минимальный или максимальный элемент.3. Пример на Swift:func quickSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }
    let pivot = array[array.count/2]
    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let greater = array.filter { $0 > pivot }
    return quickSort(less) + equal + quickSort(greater)
}Вывод:Быстрая сортировка эффективна для больших данных, но требует аккуратного выбора pivot.