c++ - 使用 Hoare 分区的快速排序

Question

在阅读有关它的维基百科文章后，我在 C++ 中实现了快速排序。只是想重温我在学校为换工作面试做准备的内存。

这是我的实现

#include <vector>

size_t partition(std::vector<int> & inputs, size_t leftIndex, size_t rightIndex)
{
    int pivotValue = inputs[leftIndex];
    size_t i = leftIndex - 1;
    size_t j = rightIndex + 1;

    while (true)
    {
        while (inputs[++i] < pivotValue);
        while (inputs[--j] > pivotValue);

        if (i >= j)
        {
            return j;
        }

        std::iter_swap(inputs.begin() + i, inputs.begin() + j);
    }

    return 0;
}

void sort(std::vector<int> & inputs, size_t leftIndex, size_t rightIndex)
{
    if (leftIndex < rightIndex)
    {
        size_t pivot = partition(inputs, leftIndex, rightIndex);
        sort(inputs, leftIndex, pivot);
        sort(inputs, pivot + 1, rightIndex);
    }
}

int main()
{
    std::vector<int> inputs = { 3,7,1,2,9,5,4,0,8,6 };
    sort(inputs, 0, inputs.size() - 1);

    return 0;
}

到目前为止，它似乎适用于我提出的所有测试输入。

为清楚起见从此处编辑

如果我们改变

        if (i >= j)
        {
            return j;
        }

到

        if (i > j)
        {
            return j;
        }
        else if(i == j)
        {
            return j;
        }

我的问题是，哪一组输入会执行以下分区函数 block ？

        if (i > j)
        {
            return j;
        }

Answer 1

出现了困惑，因为我错误地实现了算法。正如一些用户在对原始问题的评论中指出的那样(编辑前)，维基百科上的列表使用 do/while 而不是 while，这样 i 的增加和 j 的减少发生在条件评估之前.

我原以为没有功能差异，但确实存在。

因此，给定一个等价的配分函数:

size_t partition(std::vector<int> & inputs, size_t leftIndex, size_t rightIndex)
{
    int pivotValue = inputs[leftIndex];
    size_t i = leftIndex - 1;
    size_t j = rightIndex + 1;

    while (true)
    {
        while (inputs[++i] < pivotValue);
        while (inputs[--j] > pivotValue);

        if (i >= j)
        {
            return j;
        }

        std::iter_swap(inputs.begin() + i, inputs.begin() + j);
    }

    return 0;
}

很明显，当循环将标记指向同一个元素或彼此交叉时，循环将标记在靠近中间的每个边界上移动后，对 i >= j 的检查将获得真正的命中。

通过修复递增和递减循环，递增和递减发生在主循环的每次迭代中。而以前，他们没有。

一如既往，在处理算法时，在纸上一步步走下去，它就会变得清晰。