分區循環理解

爲什麼分區方法的循環體不會拋出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

分區循環理解

回答

相關問題