-1

我很难实现 Hoare 的分区算法。基本上，我想要做的是将一个数组分成两部分，第一部分包含小于给定的数字x，另一部分包含更大的数字。但是，我只是想不出一个好的实现。这是我的代码：

void hoare(vector<int>&arr,int end, int pivot)
{
    int i = 0;
    int j = end;

    while (i < j)
    {
        while (arr[i] < pivot)
            i += 1;

        while (arr[j] > pivot)
            j -= 1;            

        swap(arr[i],arr[j]);
    }

    // return arr;
    for (int i=0; i<end; i++)
    printf("%d ", arr[i]);
}

现在我发现很多网站都有 while 而(arr[i] <= pivot)不是我放在那里的。但是，当我这样做时，对于这样的数组：

1 3 5 7 9 2 4 6 8

我得到：

1 3 5 4 9 2 7 6 8

但话又说回来，在我的版本中，对于这样一个集合：

12 78 4 55 4 3 12 1 0

程序冻结，因为由于外部循环中的条件都没有得到满足，所以它只是一遍又一遍地遍历它，而不增加jor i。

枢轴是指向数组中特定数字的指针，从 1 开始计数；例如，在第一个示例中传递给函数的数字 3 表示pivotequals arr[2]，即 5

抱歉，如果这是一个菜鸟问题或已经回答，但我已经花了一整天的时间（也在网上寻找解决方案）无济于事，现在我有自杀的念头。

提前致谢。

4

1 回答 1

2

当然，对序列进行分区的简单答案是使用

auto it = std::partition(vec.begin(), vec.end(),
                         std::bind2nd(std::less<int>(), pivot));

该函数并不真正关心谓词，而是将序列重新排列为两个序列：一个由谓词产生true，另一个由谓词产生false。该算法将迭代器返回到第一个子序列的末尾（由谓词为 的元素组成true）。有趣的是，该算法应该在前向迭代器上工作（如果它真的得到前向迭代器，它可以使用相当多的交换）。您正在实现的算法显然需要双向迭代器，即，我将忽略也适用于正向序列的要求。

在实现算法时，我会遵循完全相同的接口，因为迭代器抽象对于序列算法非常有效。算法本身只是简单地用于在范围内std::find_if()查找迭代器，使得谓词不成立：it[begin, end)

it = std::find_if(begin, end, not1(pred));

如果存在这样的迭代器，它std::find_if()会搜索[std::reverse_iterator<It>(end), std::reverse_iterator<It>(it))一个迭代器rit，使得谓词确实成立：

rit = std::find_if(std::reverse_iterator<It>(end), std::reverse_iterator<It>(it),
                   pred);

如果存在这样的迭代器，则它std::swap()是相应的位置并更新begin，end因此：

std::swap(*it, *rit);
begin = ++it;
end = (++rit).base();

如果找到it或未rit找到，则算法终止。将此逻辑放入一致的算法中似乎相当简单。请注意，此算法甚至不能使用您尝试使用的运算符，即概念上元素只能与x < pivotand进行比较x >= pivot（与 相同!(x < privot)）。

下面的实现未经测试，但完整的算法看起来像这样：

template <typename BiIt, typename Pred>
BiIt partition(BiIt it, BiIt end, Pred pred) {
    typedef std::reverse_iterator<BiIt> RIt;
    for (RIt rit(end);
         (it = std::find_if(it, end, std::not1(pred))) != end
         && (rit = std::find_if(RIt(end), RIt(it), pred)) != RIt(it);
         ++it, end = (++rit).base()) {
         std::swap(*it, *rit);
    }
    return it;
}
于 2012-12-25T19:08:54.430 回答