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