RandomizedQuickSort算法的實現

Question

我想實現RandomizedQuickSort算法。我認爲我正確執行了randomizedPartition方法，但我不知道排序方法有什麼問題？！

這裏是我的嘗試：

public class RandomizedQuickSort { 
    public static void sort(int[] A, int start, int end) { 
     if(start < end) { 
      int pivot = randomizedPartition(A, start, end); 

      sort(A, start, pivot - 1); 
      sort(A, pivot + 1, end); 
     } 
    } 

    private static int randomizedPartition(int[] A, int start, int end) { 
     int pivot = A[start]; 
     int pivotIndex = start; 

     for(int i = start + 1; i < end; i++) { 
      if(A[i] <= pivot) { 
       pivotIndex += 1; 
       swap(A, pivotIndex, i); 
      } 
     } 
     swap(A, start, pivotIndex); 

     return pivotIndex; 
    } 

    private static void swap(int[] A, int x, int y) { 
     int temp = A[x]; 

     A[x] = A[y]; 
     A[y] = temp; 
    } 

    public static void main(String[] args) { 
     int A[] = {11, 0, 2, 8, 15, 12, 20, 17, 5, 11, 1, 16, 23, 10, 21, 7, 22, 9}; 

     sort(A, 0, A.length); 

     for(int i = 0; i < A.length; i++) { 
      System.out.print(A[i] + ", "); 
     } 
     System.out.println(); 
    } 
} 

這是我得到的輸出：

0, 1, 2, 8, 5, 9, 10, 11, 7, 11, 12, 16, 17, 15, 20, 21, 22, 23 

Answer 1

那麼，除了這個事實，你是不是隨機選擇一個支點，你必須關閉的情況排序子陣列時出現一個錯誤。請注意，您的第一個排序呼叫是sort(A, 0, A.length)，因此結束索引是A.length - 1。因此，第一個子陣列應該高達pivot，而不是pivot - 1。它的固定如下：

public static void sort(int[] A, int start, int end) { 
    if(start < end) { 
     int pivot = randomizedPartition(A, start, end); 

     sort(A, start, pivot); // This line needed to be changed! 
     sort(A, pivot + 1, end); 
    } 
} 

輸出：

0, 1, 2, 5, 7, 8, 9, 10, 11, 11, 12, 15, 16, 17, 20, 21, 22, 23,