java - 分区循环理解

Question

为什么分区方法的循环体从不抛出 ArrayIndexOutOfBounds 异常？

public static int partition( int[] a, low, high ) {

    int k = low, m = low;


    /* loop invariant:
    *     low <= k <= m <= high  and
    *     all elements in a[low..k-1] are RED (i.e., < pivot) and
    *     all elements in a[k..m-1] are BLUE (i.e., >= pivot)
    */
    while (m != high)  {
       if (a[m] >= pivot)     // a[m] is BLUE
          { }
       else  {                // a[m] is RED
          swap(a,k,m);
          k = k+1;
       }
       m = m+1;
    }
    return k;
 }

Answer 1

// m <= high (loop invariant)
while (m != high)  {
    // m < high, hence correct index
    a[m] ...

    m = m + 1;
    // m <= high (loop invariant)
}

思想交换不会改变 m。也许你认为 k 和 m 交换了，但可能是 a[k] 和 a[m]。因为 m 是一个局部 int 变量，而 int 是按值传递的。

即使 m 和 k 交换：m <= high

循环不变量 k <= m 保持不变：

// k <= m
if (...) {
    swap(a, k, m);
    // m <= old m // if call-by-reference

    k = k + 1;
    // k - 1 <= m if call-by-value
}
m = m + 1;
// k <= m again; if call-by-value