考慮到第一個元素作爲支點，爲什麼索引不會超出數組的邊界？

Question

在分區分區的兩個while循環中，爲什​​麼看起來索引i是否超出了數組的邊界並沒有被視爲一見鍾情？[這是來自Big Java的正確代碼，我已經測試過了，只是該指數的東西混淆了我]

public void sort(int from, int to) 
    { 
     if (from >= to) return; 
     int p = partition(from, to); 
     sort(from, p); 
     sort(p + 1, to); 
    } 

    private int partition(int from, int to) 
    { 
     int pivot = a[from]; 
     int i = from - 1; 
     int j = to + 1; 
     while (i < j) 
     { 
     i++; while (a[i] < pivot) i++;//here 
     j--; while (a[j] > pivot) j--;//here 
     if (i < j) swap(i, j); 
     } 
     return j; 
    } 

Answer 1

在你的主partition循環中，您可以看到i和j開始在陣列的兩端，朝向pivot工作，而在該位置的元素是<或>支點。他們都必須停止選擇的樞軸，以便他們永遠不會逃脫陣列。

int[] a; 

private void sort() { 
    sort(0, a.length - 1); 
} 

public void sort(int from, int to) { 
    if (from >= to) { 
     return; 
    } 
    int p = partition(from, to); 
    sort(from, p); 
    sort(p + 1, to); 
} 

private int partition(int from, int to) { 
    int pivot = a[from]; 
    int i = from - 1; 
    int j = to + 1; 
    while (i < j) { 
     i++; 
     while (a[i] < pivot) { 
      i++; 
     } 
     j--; 
     while (a[j] > pivot) { 
      j--; 
     } 
     if (i < j) { 
      swap(i, j); 
     } 
    } 
    return j; 
} 

private void swap(int i, int j) { 
    int t = a[i]; 
    a[i] = a[j]; 
    a[j] = t; 
} 

public void test() { 
    System.out.println("Hello"); 
    a = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; 
    sort(); 
    System.out.println(Arrays.toString(a)); 
} 

注意，使用numbers[low]爲支點僅僅降低性能 - 算法仍然正確排序的數組。

Answer 2

在第一次迭代中，兩個索引都不能通過pivot元素，因爲i < pivotIndex < j。因此，您無法在第一次迭代中通過界限（提供的索引位於有效範圍內並且from <= to;索引在循環之前的遞增/遞減語句之後也在範圍內）。

在所有迭代後的第一個的索引不能變得比from小於或大於to時，由於i < j和swap -call在最後循環迭代放置，使得各循環條件false在索引i和j分別的元件：對於位置爲j的元素a[j] > pivot爲假，但該元素已移至位置i < j，位置爲i的元素a[i] < pivot爲假，但該元素已移至位置j > i。

Answer 3

由於主鍵是從相同的數組中選擇的，並且由於算法的邏輯如何實現，因此您無需檢查索引是否超出界限。在執行的某個時刻，條件必須變爲真。

算法的正確性可以用循環不變式來證明。

1. private int partition(int from, int to) 
2. { 
3. int pivot = a[from]; 
4. int i = from - 1; 
5. int j = to + 1; 
6. while (i < j) 
7. { 
8.  i++; 
9.  // at least one of a[i]...a[to] is greater than or equal to pivot 
10.  while (a[i] < pivot) i++; 
11.  j--; 
12.  // at least one of a[from]...a[j] is less than or equal to pivot 
13.  while (a[j] > pivot) j--;//here 
14.  if (i < j) swap(i, j); 
15.  // if i < j then at least one of a[i + 1]...a[to] is greater than or equal to pivot 
16.  // if i < j then at least one of a[from]...a[j - 1] is less than or equal to pivot 
17. } 
18. return j; 
19. } 

線9和12（以及15，16）包含用於環路6的每一次迭代到17.從這些不變量顯然i和j指數可以從不出門陣列保持爲真不變量界限。

我們只能證明第9行的不變量，第12行的不變量可以類似地證明。

對於第一次迭代來說，它是真的，因爲主鍵選擇爲a[from]和i = from。

在每次迭代（包括第一次迭代）結束時，我們將位置爲i的元素移動到大於或等於位置j。因爲i < j那麼第15行的不變量就成立了。在第8行增加i之後的下一次迭代中，不變量9變得有效，其直接來自不變量15.通過歸納，我們可以得出結論，不變量9在循環6至17的每次迭代中都是有效的。

如果我們選擇pivot作爲數組的最後一個元素，即[不變量]仍然保持爲真。但是，我們需要改變排序方法中的流程。

sort(from, p == to ? p - 1 : p); 
sort(p + 1, to); 

代替

sort(from, p); 
sort(p + 1, to);