java - 为正确的部分调用快速排序时，我的变量的值是多少？

Question

我正在努力理解下面快速排序实现过程中的特定部分。

具体来说，当我对枢轴的左半部分进行排序时，我应该sort(..)使用参数 j+1 到 hi 调用右半部分。

当我使用它对左半部分进行排序时，我的j不是被分区函数修改了吗？

因此j+1实际上不是在枢轴的右侧吗？我想这更多是关于理解程序流程的问题。

那么，当我打电话时jsort(a, j+1, hi)是什么？对不起，如果这是一个愚蠢的问题

// sort in ascending order
public static void sort(Comparable[] a) {
    sort(a, 0, a.length - 1);
}

private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo) {
        return;
    }
    int j = partition(a, lo, hi); 
    sort(a, lo, j-1); // Sort left part a[lo .. j-1].
    sort(a, j+1, hi); // <---- issue understanding here
}

private static int partition(Comparable[] a, int lo, int hi) {
    // Partition into a[lo..i-1], a[i], a[i+1..hi].
    int i = lo, j = hi+1; // left and right scan indices
    Comparable v = a[lo]; // partitioning item
    while (true)
    { // Scan right, scan left, check for scan complete, and exchange.
        while (less(a[++i], v)) if (i == hi) break;
        while (less(v, a[--j])) if (j == lo) break;
        if (i >= j) break;
        exch(a, i, j);
    }
    exch(a, lo, j); // Put v = a[j] into position
    return j; // with a[lo..j-1] <= a[j] <= a[j+1..hi].
}

排序 [7, 5, 1, 3, 9, 8] 时，我选择枢轴为a[0]=7。对左半部分进行排序，我得到 [1,3,5,7,9,8]，现在仍然需要为枢轴的右半部分调用 sort (7)。调用 -should- 看起来像sort(a, 3+1, 5)，但我知道它看起来像sort(a, 1+1, 5)因为我的j在排序左半部分后为 1。

标签： javaalgorithmquicksort