Java 快速排序算法问题

菜鸡如我又来问问题了，我懂快速排序的思路，但是没看懂这个方法 private static int partition(Comparable[] a, int lo, int hi)两个 while 循环是怎么配合 exch(a, i, j)，less()执行的，while(true)里代码的执行顺序是什么样的。希望大神们能指教下，多谢了！

源码 link： https://algs4.cs.princeton.edu/23quicksort/Quick.java.html

public class Quick {

// This class should not be instantiated.
private Quick() { }

/**
 * Rearranges the array in ascending order, using the natural order.
 * @param a the array to be sorted
 */
public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);
    sort(a, 0, a.length - 1);
    assert isSorted(a);
}

// quicksort the subarray from a[lo] to a[hi]
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(a, j+1, hi);
    assert isSorted(a, lo, hi);
}

// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    Comparable v = a[lo];
    while (true) { 

        // find item on lo to swap
        while (less(a[++i], v)) {
            if (i == hi) break;
        }

        // find item on hi to swap
        while (less(v, a[--j])) {
            if (j == lo) break;      // redundant since a[lo] acts as sentinel
        }

        // check if pointers cross
        if (i >= j) break;

        exch(a, i, j);
    }

    // put partitioning item v at a[j]
    exch(a, lo, j);

    // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
    return j;
}

private static boolean less(Comparable v, Comparable w) {
    if (v == w) return false;   // optimization when reference equals
    return v.compareTo(w) < 0;
}
    
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
    Object swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

ywcjxf1515

2018-12-18 08:14:10 +08:00

三个 break 都表示跳出循环，这时变一下基准数位置，就切分完毕，变成比基准数小，基准数，比基准数大三部分。第一个 break，到右边界，跳出循环，表示其他所有数都比基准数小。第二个 break，到左边界，跳出循环，表示所有其他所有数都比基准数大。while(true)内部的的第二个 while 之下的 if 的条件能成立，表示剩下所有数是前面部分比基准数大，后面部分比基准数小，同样是变一下基准数位置就切分完毕。exch(a,i,j)是放在 break 之后，有隐含条件是 if(i<j)，为了交换左边的一个和右边的一个数，最终是为了达到左边比基准数小，右边比基准数大。

ywcjxf1515

2018-12-18 09:13:15 +08:00

@wenb1 你问的 while 的应该是 while(true)内部的两个 while 吧？在得到 less 的结果为 true 时，并不会停下来，内部不是还有一个 if，停下来要么是 if 的 break 执行了，要么是 less 的结果是 false，这时 i 才不变，等着被交换。j 同理。切分的目标是左边的所有比基准数小，右边的所有比基准数大，排定基准数。为了减少交换，从左边起比基准数小，就自加序号看下一个数，直到不比基准数大(也就是 false)。