實現快速排序與中間元素作爲樞軸

Question

我試着寫了一箇中間元素作爲樞軸快速排序的代碼。

我成功地寫了一篇。

但樞軸具有這樣的特性：

在其左側元素比支點小或更大的在其右側。

我無法在我的下面的代碼中實現這一點。

private static void QuickSortAlgorithm(int[] a, int i, int n) 
{ 
    if(i<n) 
    { 
     int part = partition(a,i,n); 

     QuickSortAlgorithm(a, i, part-1); 

     QuickSortAlgorithm(a, part, n); 
    } 
} 

private static int partition(int[] a, int i, int n) 
{ 
    int pivot = (i+n)/2; 

    int left = i; 

    int right = n; 
    while(left<=right) 
    { 
     while(a[left]<a[pivot]){ 
      left++; 
     } 

     while(a[right]>a[pivot]) 
     { 
      right--; 
     } 

     if(left<=right) 
     { 
      swap(a,left,right); 
      left++; 
      right--; 
     } 
    } 
    return left; 

} 

主要方法：

int a[]={5,7,3,9,1}; 
    int n = a.length; 
    QuickSortAlgorithm(a,0,n-1); 
    System.out.println(Arrays.toString(a)); 

我的疑問是：

我送留給我的分區索引。

但是，當我遞歸調用QuickSortAlgorithm（）

我送i to part-1和part to n;

我應該分區索引發送功能，使

我可以打電話給這樣的事情：使支點屬性是滿意嗎？

QuickSortAlgorithm(a, i, part-1); 

    QuickSortAlgorithm(a, part+1, n); 

謝謝:)

Answer 1

您可以選擇陣列中的最左邊的元素，或者你可以選擇成爲你的支點任何隨機元素。

退房的wikipedia page on quicksort爲更多細節選擇支點