GESP 2025年9月 C++五级 单选题 第11题

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. 在平均情况下，划分的递归层数为 ，每层中的总循环数为 ，总时间为 。
• C. 在最差情况下，每轮划分操作都将长度为 的数组划分为长度为 0 和 的两个 数组，此时递归层数达到 子 ，每层中的循环数为 ，总时间为 。
• D. 划分函数 partition 中“从右往左查找”与“从左往右查找”的顺序可以交换。

正确答案：D