algorithm - 快速排序的实现

Question

以下quicksort代码来自programming pearls

void qsort3(int l, int u)
{   int i, j;
    DType t;
    if (l >= u)
        return;
    t = x[l];
    i = l;
    j = u+1;
    for (;;) {
        do i++; while (i <= u && x[i] < t);
        do j--; while (x[j] > t);
        if (i > j)
            break;
        swap(i, j);
    }
    swap(l, j);
    qsort3(l, j-1);
    qsort3(j+1, u);
}

在双向分割部分，有一行:

if (i > j)

我的问题是我可以将此行更改为:

if(i >= j)

我认为可以这样做的原因是:(i==j) <=> (x[i] == t) 这样我们就不需要交换 x[i] 和 x[j]。我们只是打破了 for 循环。

for 循环的以下代码是swap(l, j)。由于 x[j] == t == x[l]，swap(l, j) 与做分区。

谢谢

Answer 1

我会说，是的，您可以进行更改:

当 i == j 时，swap(i, j) 是没有返回的，并且 i == j 之后的下一次迭代无条件地递增 i 并递减 j，因此将导致循环终止，无论如何都不改变数组。