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,