g5-04409. GESP-5级-2025-09-单选-第11题 未做

下述 C++ 代码实现了快速排序算法，下面说法错误的是（ ）。

int partition(vector<int>& arr, int low, int high) {
    int i = low, j = high;
    int pivot = arr[low];                 // 以首元素为基准
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;   // 从右往左查找
        while (i < j && arr[i] <= pivot) i++;   // 从左往右查找
        if (i < j) swap(arr[i], arr[j]);
    }
    swap(arr[i], arr[low]);
    return i;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low >= high) return;
    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
}

• A. 快速排序之所以叫“快速”，是因为它在平均情况下运行速度较快，常数小、就地排序，实践中通常比归并排序更高效。
• B. 在平均情况下，划分的递归层数为 $O(\log n)$，每层中的总循环数为 $O(n)$，总时间为 $O(n\log n)$。
• C. 在最差情况下，每轮划分操作都将长度为 $n$ 的数组划分为长度为 $0$ 和 $n-1$ 的两个子数组，此时递归层数达到 $n$，每层中的循环数为 $O(n)$，总时间为 $O(n^2)$。
• D. 划分函数 partition 中“从右往左查找”与“从左往右查找”的顺序可以交换。