在Java快速排序不排序正確

Question

我有一個似乎排序給定的輸入數組，但不能完全這樣快速排序算法：

public static int partition(int[] A,int low,int high){ 
    int pivot=A[high-1]; 
    int i=low-1; 
    int temp=0; 
    for(int j=low;j<A.length-1;j++){ 
     if(A[j]<pivot){ 
      i++; 
      temp = A[j]; 
      A[j]=A[i]; 
      A[i]=temp; 
     } 
    } 
    temp=A[high-1]; 
    A[high-1]=A[i+1]; 
    A[i+1]=temp; 
    return i+1; 
} 

public static void Qsort(int[] A,int low,int high){ 
    if(low<high){ 
     int p=partition(A,low,high); 
     Qsort(A,low,p-1); 
     Qsort(A,p+1,high); 
     } 
} 

我打電話的方法快速排序主這樣

Qsort(arr,0,arr.length); 

例如此陣列正確排序

6,5,3,7,1,2 

但這一個

{6,5,3,7,1,2,4} is sorted like this {1 3 2 4 5 6 7} 

，如果我的最後一個索引更改爲8，而不是4它的工作原理。這很混亂。 我認爲錯誤是輕微的，但我找不到它。

感謝您的幫助。

編輯： 正確的解決問題的方法：

public static int partition(int[] A,int low,int high){ 
    int pivot=A[high]; 
    int i=low; 
    int temp=0; 
    for(int j=low;j<high;j++){ 
     if(A[j]<pivot){ 
     temp = A[j]; 
     A[j]=A[i]; 
     A[i]=temp; 
     i++; 
     } 
    } 
    temp=A[high]; 
    A[high]=A[i]; 
    A[i]=temp; 
    return i; 
} 

，並在主調用快速排序應該是：（很重要）

Qsort(arr,0,arr.length-1); 

感謝大家的幫助。

Answer 1

public static int partition(int[] A,int low,int high){ 
    int pivotIndex=0; 
    int pivot=A[pivotIndex]; 
    int i=low;  
    int temp=A[pivotIndex]; 
    A[pivotIndex]=A[high]; 
    A[high]=temp; 
    for(int j=low;j<high;j++){ 
     if(A[j]<pivot){ 
      temp = A[j]; 
      A[j]=A[i]; 
      A[i]=temp; 
      i++; 
     } 
    } 
    temp=A[high-1]; 
    A[high-1]=A[i+1]; 
    A[i+1]=temp; 
    return i; 
} 

有進行必要的一些改進，它的工作：

1. 選擇樞軸指數不高-1，爲簡單起見，讓我們0
2. 交換元素pivotIndex與高進入for循環
3. 之前增加您的storeIndex我交換之後，而不是之前
4. 返回的storeIndex我，而不是我++