Segunder当排序矢量时

作为一个练习，我在一个模板中实现了quicksort算法，它对于元素数量较少（高达760）的向量“正常工作”，但给出更多元素的seqfault。有人可以告诉我我做错了什么：Segunder当排序矢量时

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; 
}

来源

2012-12-28 slashmais

为什么你在堆上分配的临时引导？ –

您的递归太深，耗尽了所有可用的堆栈空间。 – DCoder

使用迭代器或索引，而不是创建一个新的向量。 – andre

正如其他人指出的那样，按升序排序数据。但是，这不是您的段错误的原因。代码中的问题是，在分区阶段您不排除主元素。

只需尝试对仅包含两个相同元素（例如，{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-28 18:51:28

这是正确的:)正确:)谢谢。（如此简单 - 我会在星期天的一个月内怀疑） – slashmais

Segunder当排序矢量时

回答

相关问题