i++ 或 j-- 在使用 java 快速排序的 while 语句中

Question

我首先使用 java:

编写了这样的快速排序分区函数

public static int partition(int[] array, int left, int right) {

    int pivot = array[left];
    int i = left;
    int j = right;

    while(i < j) {
        while(i < j && array[j--] >= pivot); // flag1
        if(i < j) array[i++] = array[j];
        while(i < j && array[i++] <= pivot); // flag2
        if(i < j) array[j--] = array[i];
    }

    array[i] = pivot;
    return i;
}

然后我测试了函数，发现使用快速排序函数时输入的数组不会改变。我对flag1和flag2中的代码存疑，于是我改了：

public static int partition(int[] array, int left, int right) {

    int pivot = array[left];
    int i = left;
    int j = right;

    while(i < j) {
        while(i < j && array[j] >= pivot)
            j--;
        if(i < j) array[i++] = array[j];
        while(i < j && array[i] <= pivot)
            i++;
        if(i < j) array[j--] = array[i];
    }

    array[i] = pivot;
    return i;
}

这次成功了。为什么第一个代码片段不起作用？

Answer 1

while(i < j && array[j--] >= pivot); // flag1

无论条件的第二个子句是否为真，这都会改变 j。

while(i < j && array[j] >= pivot)
  j--;

如果条件的第二个子句为真，这只会更改 j。

因此，它们的作用完全不同。

考虑差异的影响：您正在寻找 array 的最后一个元素 element < pivot。当 j 指向该元素时，条件变为假。

如果您应用方法 2，j 仍然指向该元素。
如果您应用方法 1，j 最终指向前一个元素；

i++ 或 j-- 在使用 java 快速排序的 while 语句中

i++ or j-- in while statement in quick sort using java

java

quicksort