单选题 适中
#19817

下面代码实现了归并排序。下述关于归并排序的说法中,不正确的是( )。 void merge ( vector < int > & arr , vector <…

下面代码实现了归并排序。下述关于归并排序的说法中,不正确的是( )。

void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) { 
    int i = l, j = mid + 1, k = l; 
    while (i <= mid && j <= r) { 
        if (arr[i] <= arr[j]) temp[k++] = arr[i++]; 
        else temp[k++] = arr[j++]; 
    } 
    while (i <= mid) temp[k++] = arr[i++]; 
    while (j <= r) temp[k++] = arr[j++]; 
    for (int p = l; p <= r; p++) arr[p] = temp[p]; 
} 
void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) { 
    if (l >= r) return; 
    int mid = l + (r - l) / 2; 
    mergeSort(arr, temp, l, mid); 
    mergeSort(arr, temp, mid + 1, r); 
    merge(arr, temp, l, mid, r); 
}


未登录也能判分,登录后才会记录
答案与解析
正确答案:C
解析
归并排序通过分治法将数组递归分割至单个元素,再逐层合并有序子序列。每次合并操作比较两个已排序子区间元素,按序放入临时数组,最终复制回原数组。递归深度为logn量级,每层合并总耗时O(n),整体时间复杂度由递归树结构决定。算法执行过程中需辅助数组存储中间结果,空间开销与输入规模成正比。无论数据初始分布如何,拆分与合并过程的行为保持一致,其时间复杂度在最坏、平均和最好情况下均相同。大规模数据处理中,该算法表现出稳定的性能特征。