单选题 适中
#19818

下述C++代码实现了快速排序算法,最坏情况的时间复杂度是( )。 int partition ( vector < int > & arr , int low…

下述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); 
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:C
解析
分析分区函数的划分逻辑,观察基准元素的选择方式及其在序列中的位置变化。考察每次划分时左右子区间的规模分布,特别是当输入序列已有序或逆序时,基准元素是否总位于子区间一端。根据递归调用的深度与每层处理的数据量,推导出总的比较和移动操作次数的增长趋势。结合划分过程的循环执行次数与递归树的层数,确定时间复杂度的上界表达式。