algorithm - 快速排序的实现

Question

以下快速排序代码来自编程珍珠

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，因此将导致循环终止而不会改变数组。