Quicksort没有做任何事情，现在陷入永久循环

  • Z时代
  • 2024-01-10
  • 分类：问答

我试图实施就地版本的quicksort。这是我的代码：Quicksort没有做任何事情，现在陷入永久循环

#include <vector> 
#include <algorithm> 
using namespace std; 
size_t partition(vector<int>& v, size_t l, size_t r, size_t p) 
{ 
    size_t pivot = v[p]; 
    swap(v[p], v[r]); 
    size_t store = l; 
    for (size_t i = l; l < (r-1); i++) { 
     if (v[i] <= pivot) { 
      swap(v[i], v[store]); 
      store++; 
     } 
    } 
    swap(v[store], v[r]); 
    return store; 
} 
void quickSort(vector<int>& v, size_t l, size_t r) 
{ 
    //If two or more elements 
    if(l<r) 
    { 
     size_t pI = l; 
     size_t nP = partition(v, l, r, pI); 
     quickSort(v, (nP+1), r); 
     quickSort(v, l, (nP-1)); 
    } 
}

仅供参考，我使用的是伪代码in-place version on wikipedia。

我遇到的问题是，我第一次accredntily调用列表中间的函数作为最左arguemtn。该程序运行无错误，并输出新的列表，完全不变和未排序（根本没有错误）。我发现我的错误，现在我这样调用该函数：

quickSort(v, 0, (v.size()-1));

而且Xcode的警告我说，我被陷在一个永远的循环在

if (v[i] <= pivot)

这是在确切的路线，如如果比较触发某事。如果你能帮助我，我会很高兴！

回答：

您的问题是，您正在比较l < r - 1，但在for循环的每次迭代中增加了i。因此，无限循环。将for (size_t i = l; l < (r-1); i++) {更改为for (size_t i = l; i < (r-1); i++) {。

以上是 Quicksort没有做任何事情，现在陷入永久循环 的全部内容， 来源链接： utcz.com/qa/266317.html

回到顶部