爲什麼在QuickSort實現中將大部分元素設置爲最右邊的元素不起作用？

Question

我將QuickSort的當前實現設置爲數組中的最後一個元素，導致堆棧溢出異常。將它設置爲中間元素，或者最左邊，可以正常工作，但不是正確的。我真的想明白爲什麼。

我目前正在學習數據結構和算法，我真的很想了解算法如何工作的複雜性。我試過了下面的問題，但遞歸正在殺死我。

基本上我將我的透視設置爲數組中的最後一個元素，並找到所有小於透視並增加左邊以成爲牆。所有更大的元素都交換到正確的位置。

這裏是我的解決方案

public static void QuickSort_Recursive(int[] array, int left, int right) 
    { 

     // only proceed if left is less than right 
     if(left < right) 
     { 
      // get index for left and right barrier 
      int pivotIndex = Partition(array, left, right); 

      // sort left 
      QuickSort_Recursive(array, left, pivotIndex - 1); 

      // sort right 
      QuickSort_Recursive(array, pivotIndex, right); 
     } 
    } 

    public static int Partition(int[] array, int left, int right) 
    { 
     // get pivot as last element    
     int pivot = array[right]; 

     // continue until left passes right 
     while (left <= right) 
     { 
      // continue with left side until you find an element greater than pivot 
      while(array[left] < pivot) 
      { 
       left++; 
      } 

      // Continue with right until you find an element less than the pivot 
      while(array[right] > pivot) 
      { 
       right--; 
      } 

      // Only swap if left is less than right 
      if(left <= right) 
      { 
       // swap left and right 
       Swap(array, left, right); 

       // Increment left and decrement right 
       left++; 
       right--; 
      } 

     } 

     return left; 
    } 

誰能幫助我瞭解爲什麼它設置爲最元素導致堆棧溢出異常的權利？

編輯：下面是不與樞軸是工作實現最右邊的，但他們關鍵就在這一個是1）它不包括交換，直到最後2樞軸）只移動左指針，以便跟蹤低位和高位之間的障礙3）不會移動兩個指針

 // Make starting pivot the last one for now 
     int pivot = array[right]; 
     int leftWall = left; 

     // Go through array until index before pivot is reached 
     for (int i = left; i < right; i++) 
     { 
      // If item at array[i] is less than or equal to pivot then switch with leftwall 
      if(array[i] <= pivot) 
      { 
       // Swap positions with leftWall 
       Swap_Memory(array, i, leftWall); 

       // Increment leftwall position 
       leftWall += 1; 
      } 
     } 

     // Swap pivot with whatever value is the top lowest number (pivot is 'right' in this case) 
     Swap_Memory(array, leftWall, right); 

     // return leftwall as pivot 
     // Leftwall is barrier between values lower than pivot and those higher 
     return leftWall; 

Answer 1

問題出在您的分區實施中。 您必須以這樣的方式進行分區，以便樞軸索引左側的所有元素都應小於pivot元素。 以下兩件事必須在代碼中解決：

• 所有的比較，應該基於樞軸而不是索引。
• 此外，返回值應該是選定的元素的索引。

標準快速排序的分區看起來類似如下：

public static void QuickSort_Recursive(int[] array, int left, int right) 
    { 

     // only proceed if left is less than right 
     if(left < right) 
     { 
      // get index for left and right barrier 
      int pivotIndex = Partition(array, left, right); 

      // sort left 
      QuickSort_Recursive(array, left, pivotIndex-1); 

      // sort right 
      QuickSort_Recursive(array, pivotIndex+1, right); 
     } 
    } 

    public static int Partition(int[] array, int left, int right) 
    { 
     // get pivot as last element    
     int pivot = array[right]; 

     int i = left - 1; 

     for (int j = left; j <= right - 1; j++) { 
     if (array[j] <= pivot) { 
      i++; 
      // Make sure all the elements left of pivot index is less 
      swap(array[i], array[j]); 
     } 
     } 

     //Move the pivot to the selected index and return its index 
     swap(array[i+1], pivot); 

     return i + 1; 

    } 

希望它能幫助！