Быстрая сортировка (QuickSort) в среднем работает за время O(n log n), где n — количество элементов в массиве. Это достигается за счёт рекурсивного разбиения массива на подмассивы вокруг опорного элемента (pivot), после чего каждый подмассив сортируется отдельно.

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

Пример на C#:

void QuickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
    QuickSort(arr, left, j);
    QuickSort(arr, i, right);
}

Таким образом, быстрая сортировка — эффективный алгоритм с хорошей средней производительностью, но требует аккуратного выбора опорного элемента для избежания худших случаев.

Какая сложность у быстрой сортировки (QuickSort)?