GESP 5级客观题｜分治与递归｜课堂讲解

考试频率：高频。本卷共 2 题。

1. 归并排序和快速排序都采用递归实现，也都是不稳定排序。

   {{ select(1) }}

• 正确
• 错误

2. 下述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); 
}

{{ select(2) }}

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