c++ - 排序 vector 时出现段错误

Question

作为练习，我在模板中实现了快速排序算法，它对元素数量较少(最多约 760)的 vector “工作正常”，但对元素数量较多的 vector 给出了 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

正如其他人所指出的，您的实现效率不高，例如排序升序数据。但是，这不是您的段错误的原因。您的代码中的问题是您没有在分区阶段排除数据透视元素。

简单地尝试对仅包含两个相同元素(例如，{0,0})的 vector 进行排序。它将无限循环。

要解决此问题，请在对两个 vector 进行排序后插入主元元素。

也许这行得通(至少它修复了堆栈溢出):

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