<分区>
我正在尝试实现就地版本的快速排序。这是我的代码:
#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 的伪代码.
我遇到的问题是我一开始不小心调用了列表中间的函数作为最左边的arguemtn。该程序运行无误并输出了新列表,完全未更改且未排序(完全没有错误)。我发现了我的错误,现在我这样调用函数:
quickSort(v, 0, (v.size()-1));
Xcode 警告我,我陷入了一个永远的循环中
if (v[i] <= pivot)
就在那条确切的线上,好像比较触发了什么。如果你能帮助我,我会很高兴!