將此Quicksort實現的比較器從<=更改爲<將導致無限遞歸。爲什麼？

Question

我正在研究下面的Quicksort實現（來自破解編碼採訪）。

在分區方法中，有兩個「left < = right」謂詞（在其第一個while語句和最後一個if語句中）。當left == right時，在這些索引處交換元素將與沒有交換相同，所以我認爲去除比較的「==」部分不會有任何影響。但是，當我這樣做並運行代碼而不是「right < right」時，程序將無限（在某些輸入上）遞歸併導致堆棧溢出。爲什麼？

澄清：我在分區方法中，在（1）第一個while語句和（2）final if語句中更新了「left < = right」謂詞爲「right < right」。

否則，解決方案在使用「left < = right」時工作正常。

P.S.由於「left」在最後一個if語句中增加了，我也嘗試返回left + 1，但這仍然會導致無限遞歸。

public static void quickSort(int[] arr, int left, int right) { 
    int index = partition(arr, left, right); 
    if (left < index - 1) { // Sort left half 
     quickSort(arr, left, index - 1); 
    } 
    if (index < right) { // Sort right half 
     quickSort(arr, index, right); 
    } 
} 

public static int partition(int[] arr, int left, int right) { 
    int pivot = arr[(left + right)/2]; // Pick a pivot point. Can be an element   
    while (left <= right) { 
     // Find element on left that should be on right 
     while (arr[left] < pivot) { 
      left++; 
     } 

     // Find element on right that should be on left 
     while (arr[right] > pivot) { 
      right--; 
     } 

     // Swap elements, and move left and right indices 
     if (left <= right) { 
      swap(arr, left, right); 
      left++; 
      right--; 
     } 
    } 
    return left; 
} 

public static void swap(int[] array, int i, int j) { 
    int tmp = array[i]; 
    array[i] = array[j]; 
    array[j] = tmp; 
} 

Answer 1

我們來看一個簡單的例子，其中排序的數組是{1, 2}。當第一次調用quicksort時left是0，right是1。這些值將被轉發至partition，其中pivot將爲1。由於arr[right] > pivotright將遞減，但left保持不變。

由於while循環在分區left < right的末尾是false，所以沒有任何交換，因爲它具有相同的條件，所以循環將退出。 partition將返回left，這是0並分配給index。

Next quicksort將跳過第一個分支，因爲left < index - 1爲false。第二個分支自index < right開始執行，quicksort分別爲index和right，其值分別爲0和1。現在，如果我們在開始時看到quicksort最初被稱爲具有完全相同的值，這就解釋了無限遞歸。

如果返回left + 1，而不是那麼index將2輸入{1, 1}第一分區後，你將在quicksort恰好有同樣的問題與第一個分支。