1

作为一个练习，我在模板中实现了快速排序算法，它对于元素数量较少（最多约 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;
}
4

1 回答 1

4

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

只需尝试对仅包含两个相同元素的向量进行排序（例如，{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
于 2012-12-28T18:51:28.957 回答