单选题 适中
#20467

考虑以下C++代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是?( ) int partition ( vector < int > & a…

考虑以下C++代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是?( )

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 基准值
    int i = low - 1;
    for (int j = low; j < high; j++) {
        ____________________ // 在此处填入代码
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}
// 快速排序
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析

快速排序是一种分治算法,其基本步骤如下:

选择基准:从数组中选择一个元素作为基准(通常选择最后一个元素)。

分区:重新排列数组,使得所有比基准小的元素放在基准前面,所有比基准大的元素放在基准后面。分区完成后,基准就位于其最终排序后的正确位置。

递归排序:递归地对基准前后的子数组进行快速排序。

在分区过程中:

i初始化为low - 1,表示小于基准的区域最初为空。

j从low到high - 1遍历数组。

如果arr[j]小于pivot,则i增加1,并将arr[i]和arr[j]交换。这样,arr[i]现在是一个小于pivot的元素。

本题答案为选项B。