GESP 五级 · GESP 202312 C++ 五级 第 7 题

下面的 C++ 代码实现对 list 的快速排序，有关说法，错误的是（ ）。

vector<int> operator + (vector<int> lA, vector<int> lB)
{
    vector<int> lst;
    for (int i = 1; i < lA.size(); i++)
        lst.push_back(lA[i]);
    for (int i = 1; i < lB.size(); i++)
        lst.push_back(lB[i]);
    return lst;
}

vector<int> qSort(vector<int> lst)
{
    if (lst.size() < 2)
        return lst;
    int pivot = lst[0];
    vector<int> less, greater;
    for (int i = 1; i < lst.size(); i++)
        if (lst[i] <= pivot) less.push_back(lst[i]);
        else greater.push_back(lst[i]);
    for (int i = 1; i < lst.size(); i++)
        if (lst[i] <= pivot) less.push_back(lst[i]);
        else greater.push_back(lst[i]);
    return _________________________;
}

这题考快速排序的递归拆分与vector拼接。拿到题先看operator+只接两个vector，pivot是int，所以拼接时必须显式转成vector，否则类型不匹配编译不过，这是解题突破口。

学生最容易忽略operator+的参数类型，看到快速排序公式就机械地拼，以为pivot直接加进去就行，结果选D。其实pivot是int，operator+不支持int+vector，必须用强制类型转换。另外，operator+的实现里循环从1开始，是把0号元素（pivot）去掉了，所以拼接时pivot必须单独处理，不能漏。

【考点】运算符重载｜vector容器拼接｜递归拆分

1. 快速排序的递归结构

快速排序的核心是“分治”：选一个基准值pivot，把数组分成小于等于pivot的left部分和大于pivot的right部分，然后分别递归排序，最后把三部分拼起来。代码里已经实现了分治过程：

int pivot = lst[0];
vector<int> less, greater;
for (int i = 1; i < lst.size(); i++)
    if (lst[i] <= pivot) less.push_back(lst[i]);
    else greater.push_back(lst[i]);

这里pivot是lst[0]（int类型），less和greater都是vector<int>。