关于下述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);
}
}
在 randomPartition 函数中,变量 i 的作用是记录大于基准值的元素的边界
randomPartition 函数随机选择基准值,可以避免输入数据特定模式导致的最坏情况下时间复杂度O(n2)
快速排序平均时间复杂度是O(n log n)
快速排序是稳定排序算法