有毛病我快速排序

我下面的代碼的快速排序：有毛病我快速排序

typedef struct tagDataPair { 
    int c_value; 
    float error; 
} DataPair; 

void SortByErrorQS(std::vector<DataPair>& points, int left, int right) 
{ 
    std::vector<int> stack; 
    stack.push_back(left); 
    stack.push_back(right); 
    while(stack.size() > 0) 
    { 
     right = stack.back(); 
     stack.pop_back(); 
     left = stack.back(); 
     stack.pop_back(); 

     float pivot = (points.at(left).error + points.at(right).error + points.at((left + right)>>1).error)/3; 
     int i = left, j = right; 
     DataPair temp; 
     while(i < j) 
     { 
      while(points.at(i).error <= pivot && (i <= right)) 
       ++i; 
      while(points.at(j).error > pivot && (j > left)) 
       --j; 
      if(i <= j) 
      { 
       temp = points[i]; 
       points[i] = points[j]; 
       points[j] = temp; 
       i++; j--; 
      } 
     } 

     if(left < j) 
     { 
      stack.push_back(left); 
      stack.push_back(j); 
     } 
     if(i < right) 
     { 
      stack.push_back(i); 
      stack.push_back(right); 
     } 
    } 
}

出於某種原因，這是停留在一個無限循環，我只是無法弄清楚什麼錯誤，或者說爲什麼。有人能幫我指點這裏發生了什麼？

來源

2013-02-21 SinisterMJ

是否有你使用自己的排序功能，而不是['的std :: sort']（http://en.cppreference.com/w/cpp/algorithm/sort）？ – 2013-02-21 18:01:59

我真的不知道如何使用自定義結構實現std :: sort。我的向量需要包含那些DataPairs。 – SinisterMJ 2013-02-21 18:04:23

你會接受使用'std :: sort'的解決方案嗎？ DataPair應該如何訂購？ – 2013-02-21 18:06:04

要使用std::sort和您的DataPair結構，您可以提供自定義比較器。在C++ 11，這可以用一個lambda函數來完成：

std::sort(points.begin(), points.end(), [](const DataPair& a, const DataPair& b) { 
    return a.error < b.error; 
});

這將在error增加順序DataPair有幾分。

的C++ 03的方法是提供一個比較功能：

bool compare(const DataPair& a, const DataPair& b) 
{ 
    return a.error < b.error; 
} 

std:sort(points.begin(), points.end(), compare);

的的std::sort複雜保證是O(NlogN)。常用的實現使用快速排序或introsort。

來源

2013-02-21 18:10:58

非常感謝，作品像一個魅力！ – SinisterMJ 2013-02-21 18:43:54

有毛病我快速排序

回答

相關問題