AI题库 · GESP-C++五级题库
题目分享 #19818
下述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
O(n)
B
O(logn)
C
O(n^2)
D
O(nlogn)
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。