與快速排序算法混淆

Question

我正在實現一個快速排序算法，併成功地將輸入數組圍繞一個關鍵點進行了分區。問題是，我很困惑如何使用相同的輸入數組遞歸地對數組的第一部分和第二部分進行排序（即指定範圍）。 下面是我實現

class QuickSort { 

    int i; 
    int l = 0; 

    public void quicksort(int A[], int n) { 

     if (n == 1) { 
      return; 
     } else { 
      partition(A, 0, n); 
//----Confused as from this point 
      quicksort(A, A[i]); 

      //Recursively sort both parts of the array 
     } 
    } 

    public int partition(int A[], int l, int r) { 
     int p = A[l];//Choose pivot 
     i = l + 1; 
     //Partition around A through P 
     for (int j = i; j < r; j++) { 
      if (A[j] < p) { 
       swap(A, i, j); 
       ++i; 
      } 
     } 
     swap(A, l, i - 1); 
     return i; 
    } 

    public void swap(int A[], int i, int j) { 
     int temp = A[i]; 
     A[i] = A[j]; 
     A[j] = temp; 
    } 
    public void display(int A[]){ 
     for (int i = 0; i < A.length; i ++){ 
      System.out.print(A[i] + " "); 
     } 
    } 
} 
class QuickSortApp{ 
    public static void main(String args[]){ 
     QuickSort quick = new QuickSort(); 
     int A[] = {6,2,7,8,4,3,5}; 
     quick.quicksort(A, A.length); 
     quick.display(A); 
    } 
} 

請，我也欣賞能夠在我的算法任何其他inefficencies糾正。謝謝

Answer 1

更改您的quicksort()簽名quicksort(int[] A, int begin, int end)

因爲，你其實根本里面partition()排序。我會做的是這樣的：

if (end-begin <= 1) { 
    return; 
} else { 
    int pivot = partition(A, begin, end); 
    quicksort(A, begin, pivot); 
    quicksort(A, pivot, end); 
} 

Answer 2

創建一個快速排序呼叫的包裝與你有另一個像quicksort(A, i, j)調用的簽名和你的呼叫從包裝將quicksort(A, 0, n)。