Quicksort遞歸

Question

所以我已經成功實現了一個快速排序，每次都使用最左側的元素作爲關鍵點。我一直在嘗試使用中間元素來實現快速排序，並且有一些複雜的結果。我一直在研究具有快速排序遞歸調用自身的示例，而不用在任何條件下包裝調用，並且，正如您可能想象的那樣，它會停留在對自身的第一次調用上。

第一次調用分區，我用正確的分區數組對樣本進行分區，然後當它接近結束時，只是在開始時一次又一次地交換兩個元素。

我嘗試的策略是從列表中選取中間元素作爲數據透視表，將它放在數組的末尾，然後進行交換索引。在完成之後，我將分支之間的數據透視一下。經過幾次傳球后看起來不錯，但正如我所提到的那樣，我很早就被卡住了，從來沒有接到應該對第二個分區進行排序的調用。

任何輕推將不勝感激 - 我也是在常規工作，如果你看到任何關閉（希望這不會導致任何問題，但我避免鴨打字這個

原始數組是

[100, 305, 2, 2002, 18, 99, 211, 30, 50, 1000, 403, 4, 400, 77]

，並在達到堆棧溢出當陣列是

[2, 4, 18, 30, 50, 99, 77, 100, 211, 1000, 403, 305, 400, 2002]

class OtherQuickSort { 

static void sort(int[] array){ 

    quickSort(array, 0, array.length - 1) 

} 

static void quickSort(int[] array, int first, int last){ 
     int pivotIndex = partition(array, first, last) 

     quickSort(array, first, pivotIndex - 1) 
     quickSort(array, pivotIndex, last) 
} 

static int partition(int[] array, int first, int last){ 
    int pivotIndex = (first + last)/2 
    int pivotValue = array[pivotIndex] 

    swapIndices(array, pivotIndex, last) 

    int indexFromRight = last - 1 
    int indexFromLeft = first 

    while(indexFromLeft <= indexFromRight){ 
     while(array[indexFromLeft] < pivotValue){ 
      indexFromLeft++ 
     } 
     while(array[indexFromRight] > pivotValue){ 
      indexFromRight-- 
     } 

     if(indexFromLeft <= indexFromRight) { 
      swapIndices(array, indexFromLeft, indexFromRight) 
      indexFromLeft++ 
      indexFromRight-- 
     } 
    } 

    swapIndices(array, indexFromLeft, last) 

    indexFromLeft 
} 

static void swapIndices(int[] array, int left, int right){ 
    int leftValue = array[left] 
    array[left] = array[right] 
    array[right] = leftValue 
} 
} 

Answer 1

您需要更新您的quickSort方法。 pivotIndex處的值已經處於排序位置，因此您不必再次傳遞它。

static void quickSort(int[] array, int first, int last){ 
    if(last > first){ 
     int pivotIndex = partition(array, first, last); 

     quickSort(array, first, pivotIndex-1); 
     quickSort(array, pivotIndex+1, last); 
    } 
}