java - 在快速排序中，为什么我们从数组外部开始递减

Question

public class QuickSort {
    public static void sort(int[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int left, int right) {
        if (right <= left) {
            return;
        }
        int j = partition(a, left, right);      
        sort(a, left, j - 1);
        sort(a, j + 1, right);
    }

    private static int partition(int[] a, int left, int right) {
        int i = left;
        int j = right+1;
        int pivot = a[left];
        while (true) {
            while (a[++i] < pivot) {
                if (i == right) {
                    break;
                }
            }
            while (a[--j] > pivot) {
                if (j == left) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, left, j);
        return j;
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;

    }

    public static void main(String[] args) {
        int[] a = { 5, 3, 1, 34, 43, 5454};
        QuickSort.sort(a);
        show(a);

    }

    private static void show(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }

    }
}

在这个例子中，int j = right+1 从数组外开始，所以我们递减 a[--j]

当我将其更改为 int j = right 并按 a[j--] 递减时，输出不一样。可能是一些简单的东西，但在过去的一个小时里一直很困惑。我不明白为什么我们不从数组的最后一个索引开始递减，例如:

{4,3,6,1,9}

int j = right 

所以 j = array[4] 然后我们说 while... array[4--] 这将变成 j=array[3] 对吗？

这不是一回事吗:right+1 and --j 和 right and j--

Answer 1

线条:

while (a[--j] > pivot) {
    if (j == left) {
        break;
    }
}

期望 j 的两个值相同。如果你把它改成

while (a[j--] > pivot) {
    if (j == left) {
        break;
    }
}

第一个引用的 j，a[j--] 将比下一个 j 高一个，j == left

如果您想进行更改，则必须将其更改为:

while (a[j--] > pivot) {
    if (j+1 == left) { //adding one back in
        break;
    }
}

我个人认为以前的代码更清晰，因为在范围之外开始一个代码是常见且可以理解的。加上一个是“繁琐的”，会让每个人都质疑它是否正确。

进行更改的最明确方法可能是:

while (a[j] > pivot) {
    if (j == left) {
        break;
    }
    j--; // waiting until the end to decrement
}

我会认为它非常干净，并且比原始版本更可取，因为您从 int j = right 开始。