快速排序：幾乎排序，但不完全。怎麼了？

Question

這是代碼。輸出是一個非常接近正確的排序數組，但有幾個元素無序。任何人都可以發現錯誤？

我很確定swap和quicksort方法是正確的，但我在這裏發佈所有的方法以防萬一。

package quicksort; 
import java.util.Random; 
import java.util.Arrays; 

public class QuickSort { 

/** 
* @param args the command line arguments 
*/ 

private static int[] u; 

public static void main(String[] args) { 

    u = makeArray(100); 
    System.out.println(Arrays.toString(u)); 

    quicksort(0, u.length - 1); 
    System.out.println(Arrays.toString(u)); 

} 

public static int[] makeArray(int n) { 

    int[] a = new int[n]; 
    int j; 
    Random r = new Random(); 

    for (int i = 0; i < n; i++) { 
     j = (r.nextInt(100) + 1); 
     a[i] = j; 
    } 

    return a; 
} 

public static int partition(int left, int right, int pivot) { 

    int p = pivot; // pivot 
    int lPt = left - 1; 
    int rPt = right + 1; 

    while (true) { 

     while ((lPt < right) && (u[++lPt] < p)); 

     while ((rPt > left) && (u[--rPt] > p)); 

     if (lPt >= rPt) { 
      break; 
     } else { 

      swap(lPt, rPt); 
      System.out.println("Swapping " + lPt + " " + rPt); 

     } 


    } 

    return lPt; 
} 

public static void swap (int a, int b) {   
    int temp = u[a]; 
    u[a] = u[b]; 
    u[b] = temp; 
} 

public static void quicksort(int l, int r) { 

    if (r - l <= 0) { 
     return; 

    } else { 

     int part = partition(l, r, u[l]); 

     quicksort (l, part - 1); 
     quicksort (part + 1, r); 

    } 
} 

}

Answer 1

問題在於分區方法。在掉期結束時，樞軸元件未被置於其正確的位置。我已經改變了方法簽名，讓您在樞軸元件的位置傳球，而不是樞軸的價值，所以在快速排序（）現在你可以這樣寫：

int part = partition(l, r, l); 

在擺動身體方法，我將pivot元素交換到該部分的末尾（通過交換右側）。因此，我們隨後忽略了這個元素，我在rPT的初始化過程中拿走了「+ 1」。然後，我在while循環之後添加了一個語句，將主元素移動到位。有了這三個更改，現在的方法如下所示：

public static int partition(int left, int right, int pivotPosition) { 

    int p = u[pivotPosition]; // pivot 

    // Move pivot to the end 
    swap(pivotPosition, right); 

    int lPt = left - 1; 
    int rPt = right; 

    while (true) { 

     while ((lPt < right) && (u[++lPt] < p)); 

     while ((rPt > left) && (u[--rPt] > p)); 

     if (lPt >= rPt) { 
      break; 
     } else { 

      swap(lPt, rPt); 
      System.out.println("Swapping " + lPt + " " + rPt); 
     } 

    } 

    // Put pivot in its place 
    swap(lPt, right); 

    return lPt; 
} 

通過這些更改，代碼適用於我。

Answer 2

你必須找到在左側列表比樞軸元素大的值，並找到在右側的列表，然後我們交換其數值越小則樞軸元素的值。

package quicksort; 
import java.util.Random; 
import java.util.Arrays; 

public class QuickSort { 
    /** 
    * @param args the command line arguments 
    */ 
    private static int[] u; 

    public static void main(String[] args) { 

     u = makeArray(10); 
     System.out.println(Arrays.toString(u)); 

     quicksort(0, u.length - 1); 
     System.out.println(Arrays.toString(u)); 

    } 

    public static int[] makeArray(int n) { 
     int[] a = new int[n]; 
     int j; 
     Random r = new Random(); 
     for (int i = 0; i < n; i++) { 
      j = (r.nextInt(100) + 1); 
      a[i] = j; 
     } 
     return a; 
    } 

    private static void quicksort(int low, int high) { 
     int i = low, j = high; 
     int pivot = u[low]; 
     while (i <= j) { 
      while (u[i] < pivot) { 
       i++; 
      } 
      while (u[j] > pivot) { 
       j--; 
      } 
      if (i <= j) { 
       exchange(i, j); 
       i++; 
       j--; 
      } 
     } 
     if (low < j) { 
      quicksort(low, j); // note here 
     } 
     if (i < high) { 
      quicksort(i, high); // note here 
     } 
    } 

    private static void exchange(int i, int j) { 
     int temp = u[i]; 
     u[i] = u[j]; 
     u[j] = temp; 
    } 
}