分区循环理解

为什么分区方法的循环体不会抛出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; 
}

来源

2012-12-01 user1795732

你给甚至不会编译代码，它如果你提供了不合适的“低”和“高”值，肯定会*抛出异常。 –

这是代码的一部分，我只对这种方法的循环体感兴趣 – user1795732

请阅读http://tinyurl.com/so-list - 基本上，你没有给我们足够的上下文。我*怀疑*你想给我们上下文中'低'和'高'，'高'和'a.length'之间的关系 - 但没有这种背景下，我们不能回答这个问题。（首先，因为如果你提供了不合适的值，它将*抛出ArrayIndexOutOfBoundsException。） –

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

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

心灵交换不会改变微米。也许你认为k和m交换，但可能是[k]和[m]。由于m是一个本地int变量，并且int按值传递。

即使m和k其中交换：M = <高

的循环不变ķ< = m是helt：

// 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

来源

2012-12-01 23:13:20

分区循环理解

回答

相关问题