尝试用 C++ 编写快速排序算法并出现错误

Question

所以我正在尝试用 C++ 编写带向量的快速排序算法。

template <typename T>
T qsort(vector<T> arr) 
{
    int mid_idx = round(arr.size() / 2);
    int root_el = arr[mid_idx];
    
    vector<T> smaller;
    vector<T> bigger;
    vector<T> equals;
    for (T i: arr)
    {
        if (arr[i] > root_el)
            bigger.push_back(arr[i]);
        else if (arr[i] < root_el)
            smaller.push_back(arr[i]);
        else
            equals.push_back(arr[i]);
    }
    return (qsort(smaller) + equals + qsort(bigger));
}

我收到这个错误：

invalid operands to binary expression ('int' and 'vector<int>') [Semantic Issue]

那你能告诉我哪里出了问题吗？

Answer 1

此 C++ 代码存在一些问题。

qsort 模板函数显然打算 return 一个向量，从最后的 return 指令开始。但它被声明为 returning 类型 T 的单个对象。

此外，向量参数通过 value 传递，这对于大型向量（重复）来说是昂贵的。我建议改为通过引用传递它。

所以我们可以将顶部声明更改为：

template <typename T>
vector<T>  qsort(vector<T>& arr) 
{

一个更根本的问题： 从代码来看，似乎每次调用 qsort 都会递归且无条件地导致另外两次调用 qsort .如果以这种方式编写函数，则程序无法终止。或者更确切地说，当它耗尽堆栈时，操作系统将杀死它 space，从而进行一些非法的内存访问。

每个递归算法都需要一些终止条件。在我们的例子中，如果数组的大小小于 2，则无事可做，因为它显然已经排序了。

所以qsort函数的开头可以这样写：

#include  <vector>
#include  <cmath>
#include  <iostream>

using  std::vector;

template <typename T>
vector<T>  qsort(vector<T>& arr) 
{
    if (arr.size() < 2)
        return arr;  // so small it is already sorted !

此外，在for循环中，变量i被用作整数索引，但被声明为类型T的对象。循环可以这样写：

    for (int i = 0; i < arr.size(); i++)
    {
        if (arr[i] > root_el)
            bigger.push_back(arr[i]);
        else if (arr[i] < root_el)
            smaller.push_back(arr[i]);
        else
            equals.push_back(arr[i]);
    }

现在，我们来到最后的 return 指令：

    return (qsort(smaller) + equals + qsort(bigger));

上面的代码行显然假设对于向量，“+”运算符表示向量连接。但实际上这在 C++ 标准中是未定义的。因此，即使在包含 <vector> 头文件之后，在范围内也没有向量“+”的定义。

此外，如果国际 C++ 标准化委员会提出标准化向量“+”的问题，将会有巨大的压力，特别是来自计算物理学界的压力，支持在 传统方式常见的数学和物理教科书。

也就是说，[10,20,30] + [2,4,6] 的值必须是 [12,24,36] 而 而不是 [10,20,30,2,4,6] 正如您的代码似乎暗示的那样。

所以我们必须手动做这个向量连接，例如，使用insert STL方法：

    auto  lts = qsort(smaller);
    auto  gts = qsort(bigger);

    // concatenate sorted vectors:
    lts.insert(lts.end(),  equals.begin(),  equals.end());
    lts.insert(lts.end(),  gts.begin(),     gts.end());

    return lts;

总的来说，以下版本的代码按预期工作：

template <typename T>
vector<T>  qsort(vector<T>& arr) 
{
    if (arr.size() < 2)
        return arr;  // so small it is already sorted !

    int  mid_idx  =  arr.size() / 2;
    T    root_el  =  arr[mid_idx];

    vector<T>  smaller;
    vector<T>  bigger;
    vector<T>  equals;

    for (int i = 0; i < arr.size(); i++)
    {
        if (arr[i] > root_el)
            bigger.push_back(arr[i]);
        else if (arr[i] < root_el)
            smaller.push_back(arr[i]);
        else
            equals.push_back(arr[i]);
    }

    auto  lts = qsort(smaller);
    auto  gts = qsort(bigger);

    // concatenate sorted vectors:
    lts.insert(lts.end(),  equals.begin(),  equals.end());
    lts.insert(lts.end(),  gts.begin(),     gts.end());

    return lts;
}

测试代码：

int main()
{

    vector<int>  v1 { 609,396,620,173, 742,996,880,125,
                      478,745,206,798, 998,124,960,175  };

    vector<int>  v2 = qsort(v1);

    for (auto m : v2) {
        std::cout << m << ' ';
    }
    std::cout << std::endl;

    return EXIT_SUCCESS;
}

程序输出：

$ ./q64784877.x
124 125 173 175 206 396 478 609 620 742 745 798 880 960 996 998 
$

效率注意事项：

您的代码创建了许多临时向量，因此动态分配了大量内存。如果您查看 traditional versions of Quicksort，代码不会分配任何额外的内存。它在初始数组中完成所有工作，但这会使算法稍微复杂一些。

此外，上面的代码使用递归到最底端，仅当子向量的大小降到1时才停止。在实践中，它可能更有效当子数组大小下降到 10 或 15 时，切换到非递归的、更简单的算法，例如 Insertion Sort。要在您的平台上测试准确的最佳阈值。

尝试用 C++ 编写快速排序算法并出现错误

Trying to write quick sort algorithm in c++ and getting error

c++

arrays

sorting

vector

qsort

效率注意事项：