单选题

关于下述C++代码的快速排序算法,说法错误的是(    )。

int randomPartition(std::vector<int>& arr, int low, int high){
    int random=low+rand()%(high-low+1);
    std::swap(arr[random],arr[high]);

    int pivot = arr[high];
    int i=low-1;

    for(int j=low;j<high; j++){
        if(arr[j]<= pivot){
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i +1;
}
void quicksort(std::vector<int>& arr,int low, int high){
    if(low<high){
        int pi =randomPartition(arr,low, high);

        quicksort(arr,low,pi-1);
        quicksort(arr,pi +1,high);
    }
}
A

在 randomPartition 函数中,变量 i 的作用是记录大于基准值的元素的边界

B

randomPartition 函数随机选择基准值,可以避免输入数据特定模式导致的最坏情况下时间复杂度O(n2)

C

快速排序平均时间复杂度是O(n log n)

D

快速排序是稳定排序算法

赣ICP备20007335号-2