分类向量时的segfault

Question

作为练习，我在模板中实现了QuickSort算法，并且对于元素数量较低的向量（最多约760），它"工作正常"，但给出了更高数量的seqfault元素。有人可以告诉我我做错了什么：

template< typename Vector, typename VecElem > void qsort(Vector *pv)
{
    if (pv->size()<=1) return;
    VecElem p;
    Vector *pvl=new Vector,*pvr=new Vector;
    p = pv->back();
    pv->pop_back();
    pvr->push_back(p);
    for (auto it=pv->begin();it!=pv->end();it++)
    {
        if (*it < p) pvl->push_back(*it);
        else pvr->push_back(*it);
    }
    qsort<Vector,VecElem>(pvl);
    qsort<Vector,VecElem>(pvr);
    if (pvl->size()) *pv = *pvl;
    if (pvr->size()) std::copy(pvr->begin(), pvr->end(), std::back_inserter(*pv));
    delete pvl;
    delete pvr;
}

Answer 1

正如其他指出的那样，例如对升数据进行排序。但是，这并不是您的segfault的原因。代码中的问题是您在分区阶段不排除枢轴元素。

只需尝试对仅由两个相同元素组成的向量（例如{0,0}）组成。它将无限地循环。

要解决问题，请在两个向量分类后插入枢轴元素。

也许这起作用（至少可以修复堆栈溢出）：

pvr->push_back(p); // remove this line
// and insert it later...
qsort<Vector,VecElem>(pvl);
qsort<Vector,VecElem>(pvr);
pvl->push_back(p); // this line is new