c++ - 尝试在 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)); }

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

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

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

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

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

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

每个递归算法都需要一些终止条件。在我们的例子中，如果数组的大小小于 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]您的代码似乎暗示的那样。

所以我们必须手动进行向量连接，例如，使用插入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 
$

效率注意事项：

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

此外，上面的代码使用递归到最底端，仅当子向量的大小减小到 1时才停止。实际上，当子阵列大小降至 10 或 15。要在您的平台上进行测试以获得确切的最佳阈值。

c++ - 尝试在 C++ 中编写快速排序算法并出现错误

问题描述

解决方案

效率注意事项：

推荐阅读