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當排序矢量時

回答

相關問題