有毛病我快速排序

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

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

有毛病我快速排序

回答

相关问题