php - Hoare 分区方案返回错误的索引

Question

我正在尝试从可以包含重复项的数组的 qsort 算法中实现 Hoare 分区方案，但是每次我修改我的代码以通过测试用例时，它都会破坏另一个。想不通我的错误。

function partition(array &$original, int $lo, int $hi): int
{
    if ($lo === $hi) {
        return $hi;
    }

    $pivot = $original[$lo];

    $i = $lo - 1;
    $j = $hi + 1;
    while (true) {
        do {
            $i++;
        } while ($original[$i] < $pivot);

        do {
            $j--;
        } while ($j > $lo && $original[$j] >= $pivot);

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

        [$original[$i], $original[$j]] = [$original[$j], $original[$i]];
    }
}

在我的测试用例中，我已经尝试用while (i < j)循环替换do...while循环， 并在其中放置带有 break 语句的反转条件，例如

while ($i < $j) {
    $i++;

    if ($original[$i] >= $pivot) {
        break;
    }
}

while ($i < $j) {
    $j--;

    if ($original[$j] < $pivot) {
        break;
    }
}

但它使用[4, 1, 7, 4, 2, 5]项返回错误的枢轴索引来破坏测试用例 #4 。

标签： phpalgorithmquicksort