快速排序功能C ++ 1参数 - 矢量

Question

我需要帮助在C ++中实现Quicksort算法。我仅限于传递一个参数，一个向量。到目前为止我有这个代码，但它没有工作，因为它说复制功能有错误。请帮我解决这个问题。谢谢。

template <class T>
vector<T> quickSort(vector<T> lst)
{
    double i = 0;
    double j = lst.size() - 2;
    double temp;
    int pivotIndex = lst.size() - 1;
    double pivot = lst[pivotIndex];

    if (lst.size() <= 1)
    {
        return lst;
    }

    while (i <= j)
    {
        while (lst[i] < pivot)
        {
            i++;
        }
        while (lst[j] > pivot)
            j--;

        if (i <= j)
        {
            temp = lst[i];
            lst[i] = lst[j];
            lst[j] = temp;
            i++;
            j--;
        }
    }

    lst[pivotIndex] = lst[i];
    lst[i] = pivot;
    pivotIndex = i;

    if (lst.size() <= 2)
        return lst;

    vector<T> left_vec, right_vec;

    vector<double>::iterator pivotIter = lst.begin() + pivotIndex;
    copy(lst.begin(), pivotIter, back_inserter(left_vec));
    copy(pivotIter + 1, lst.end(), back_inserter(right_vec));

    if (left_vec.size() > 0)
    {
        quickSort(left_vec);
        copy(left_vec.begin(), left_vec.end(), lst.begin());
    }

    if (right_vec.size() > 0)
    {
        quickSort(right_vec);
        copy(right_vec.begin(), right_vec.end(), pivotIter + 1);
    }

    return lst;
}

Answer 1

你的实现有些问题。首先，vector<T>::iterator是一个依赖。所以，在此之前使用typename。见c++ dependents。接下来，你的矢量索引应该是整数(i and j)，你可以使用模板参数T而不是double用于temp和pivot，因为我相信你的目的是使它成为通用的。

最后在执行左右快速排序时，覆盖你left_vec和right_vec。虽然我更喜欢通过引用传递。

此外，您正在执行的复制操作有效地增加了快速排序的时间复杂度。由于您只允许传递一个参数，因此交叉检查您的问题陈述是否可以使用任何全局变量或传递带矢量，低和高索引的struct。

纠正了实施。

#include <stdio.h>
#include <vector>
#include <iostream>

// should be avoided in general.
using namespace std;

template <class T>
vector<T> quickSort(vector<T> lst)
{
    int i = 0;
    int j = lst.size() - 2;
    T temp;
    int pivotIndex = lst.size() - 1;
    T pivot = lst[pivotIndex];

    if (lst.size() <= 1)
    {
        return lst;
    }

    while (i <= j)
    {
        while (lst[i] < pivot)
        {
            i++;
        }
        while (lst[j] > pivot)
            j--;

        if (i <= j)
        {
            temp = lst[i];
            lst[i] = lst[j];
            lst[j] = temp;
            i++;
            j--;
        }
    }

    lst[pivotIndex] = lst[i];
    lst[i] = pivot;
    pivotIndex = i;

    if (lst.size() <= 2)
        return lst;

    vector<T> left_vec, right_vec;

    typename vector<T>::iterator pivotIter = lst.begin() + pivotIndex;
    copy(lst.begin(), pivotIter, back_inserter(left_vec));
    copy(pivotIter + 1, lst.end(), back_inserter(right_vec));

    if (left_vec.size() > 0)
    {
        left_vec = quickSort(left_vec);
        copy(left_vec.begin(), left_vec.end(), lst.begin());
    }

    if (right_vec.size() > 0)
    {
        right_vec = quickSort(right_vec);
        copy(right_vec.begin(), right_vec.end(), pivotIter + 1);
    }

    return lst;
}

int main()
{
    vector<int> a{11, 8, 30, 21, 1, 5, 2};

    vector<int> res = quickSort(a);

    for(int  i = 0; i < res.size(); i++)
        cout<<res[i]<<" ";

    cout<<endl;

    return 0;
}