Quicksort問題（java）

Question

我試圖在java中實現幾種不同類型的quicksort，但我的實現似乎沒有任何工作。我已經瀏覽了整個互聯網，我的代碼看起來與我找到的所有代碼非常相似，所以我不知道什麼是錯的。我的代碼如下:(注意，這不是完整的，但我認爲如果我發現一個快速排序有什麼問題，其他版本也可以）編輯：我遇到的問題是數組不能排序正確。我運行一個名爲isSorted的簡單方法來告訴我數組是否正確排序。我的執行快速排序

public static void quickSort(int[] A) { 
     flag=0; 
     quickSortHelper(A, 0, A.length-1); 
    } 

public static void quickSortHelper(int [] A, int low, int high){ 
     if(low<high){ 
      if(flag==0){ 
      int q=DPartition(A, low,high,A[high]); 
      quickSortHelper(A,low,q-1); 
      quickSortHelper(A,q+1,high); 
     } 

public static int DPartition(int [] A, int low, int high,int pivot){ 
     int p=pivot; 
     int i=low; 
     int j=high-1; 
     while (i<=j){ 
      while(i<=j && A[i]<=p){ 
       i=i+1; 
      } 
      while(j>=i && A[j]>=p){ 
       j=j-1; 
      } 
      if (i<j){ 
      int temp = A[i]; 
      A[i] = A[j]; 
      A[j] = temp; 
      } 

     } 
     int temp = A[i]; 
     A[i] = A[p]; 
     A[p] = temp; 
     return i; 
    } 

Answer 1

的錯誤是在你的DPartition方法使用時，它的工作原理與其他排序方法（插入排序，堆排序等），但報告虛假。在快速排序中，您將沿特定方向移動，並且只要執行交換，就會改變移動的方向。但是，在上面的代碼中，你正在朝着兩個方向移動而不需要交換。

第一個inner-while循環找到swap的位置，但不是交換，而是從下一個inner-while開始，它開始向相反的方向移動。這是錯誤的。

您應該保留一個變量來存儲陣列中的方向。

您可以嘗試修改代碼這樣的（未測試）： -

// No need to pass `pivot` as parameter. Just use `high`. 
public static int DPartition(int [] A, int low, int high) { 
    int i=low; 
    int j=high; 
    boolean leftToRight = false; 
    boolean rightToLeft = true; 

    while (i <= j) { // Iterate till middle 

     if (leftToRight) { // Move left to right 

      while(i <= j && A[i] <= A[j]){ 
       i=i+1; // Move right until condition is satisfied 
      } 
      if (i < j) { // If `i` has not moved beyond `j`. Perform Swap 
       swap(i, j, A); // Pass index for swapping along with array. 
      } 
      leftToRight = false; // Toggle to change direction. 
      rightToLeft = true; 

     } else if (rightToLeft) { // Move right to left. 

      while(j >= i && A[j] >= A[i]){ 
       j=j-1; 
      } 
      if (j > i) { // If j has not moved beyond `i`. Perform Swap 
       swap(i, j, A); 
      } 
      rightToLeft = false; // Toggle to change the direction 
      leftToRight = true; 
     } 
    } 
    return i; // Return `index` to split. 
} 

public static void swap(int p, int q, int[] a) { 
    System.out.println("p = " + p + ", q = " + q); 
    int temp = a[p]; 
    a[p] = a[q]; 
    a[q] = temp; 
}