使用HoarePartition的快速排序得到不正確的輸出

我的作業要求我實作 Quicksort 演算法，與教科書中的偽代碼完全一樣：它指定使用 HoarePartition 進行磁區。

pivot <- A[leftMost]
i <- leftMost; j <- rightMost 1

這是我的代碼：

import java.util.Arrays;
public class Main{
   public static void main(String args[]){
      int[] array1 = {10, 4, 2, 8, 7, 3, 5, 9, 6, 1};
      int n1 = array1.length;
      System.out.print("Before sorting is: ");
      System.out.println(Arrays.toString(array1));
      System.out.printf("After sorting is: ");
      Quicksort(array1, 0, n1 -1);
      System.out.println(Arrays.toString(array1));
   } //end main

   public static void Quicksort(int[]array, int start, int end){
      if(start<end){
         int pivot = HoarePartition(array, start, end);
         Quicksort(array, start, pivot-1);
         Quicksort(array, pivot 1, end);
      }
   } //end Quicksort()

   public static int HoarePartition(int[] array, int start, int end){
      int pivot = array[start];
      int i = start;
      int j = end  1;
      while(true){
      while(array[i] < pivot)
         i  ;
      do{j--}while(array[j] > pivot)

      if(i <= j)
         return j;
      int temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      } //end while
   } //end HoarePartition()

輸出是：

Before sorting is: [10, 4, 2, 8, 7, 3, 5, 9, 6, 1]
After sorting is: [1, 3, 2, 5, 7, 4, 8, 9, 6, 10]

顯然，它沒有正確排序，我一直在思考一遍又一遍，但仍然不知道我的演算法的哪一部分是錯誤的......

uj5u.com熱心網友回復：

兩個遞回呼叫應該是：

         Quicksort(array, start, pivot);   // (not pivot-1)
         Quicksort(array, pivot 1, end);

經典霍爾隔斷

      // ...
      int i = start-1;
      int j = end  1;
      while(true){
          while(array[  i] < pivot);
          while(array[--j] > pivot);
      // ...

uj5u.com熱心網友回復：

您撰寫的代碼存在一些問題。

• 在您的第一次遞回呼叫中quicksort，應該包含樞軸邊界而不是傳遞pivot-1。

• 在您的HoarePartition方法中，您忘記移動索引i和j交換之后。

• 回傳條件不僅要檢查兩個索引是否滿足i，j還要檢查它們是否相互交叉if (i >= j) return j;

• 最里面的回圈應該寫成兩個while回圈而不是 awhile和 ado-while

public static void Quicksort(int[] array, int start, int end) {
    if (start < end) {
        int pivot = HoarePartition(array, start, end);
        Quicksort(array, start, pivot);
        Quicksort(array, pivot   1, end);
    }
}

public static int HoarePartition(int[] array, int start, int end) {
    int pivot = array[start];
    int i = start;
    int j = end;

    //Iterating until the left index crosses the right index
    while (true) {

        //Looking for an element on the left side greater than the pivot
        while (array[i] < pivot) i  ;
        
        //Looking for an element on the right side lower than the pivot
        while (array[j] > pivot) j--;

        //If the left index passed the right index, then there is no element on the left side greater then the pivot or a lower element on the right side
        if (i >= j) return j;

        //Swapping the elements greater than the pivot (left) and lower than the pivot (right) (the index haven't met yet)
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;

        i  ;
        j--;
    }
}

輸出

Before sorting is: [10, 4, 2, 8, 7, 3, 5, 9, 6, 1]
After sorting is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

uj5u.com熱心網友回復：

謝謝！我發現我做的錯誤：我在 中設定了初始值錯誤HoarePartition()，在調整了我輸入的 i、j 和回圈后，它可以正常作業！

    public static int HoarePartition(int[] array, int start, int end){
    int pivot = array[start];
    int i = start -1 ;
    int j = end   1;

    while(true){
        do{i  ;}while(array[i] < pivot);
        do{j--;}while(array[j] > pivot);
        
        if(i>=j)
            return j;
        /*swap(array[i], array[j])*/
        swapIJ(array, i, j);
    } //end while
} //end HoarePartition()

標籤：爪哇 算法 输出 快速排序 分割

上一篇：如何將一些陣列方法應用于反應中的過濾器搜索

下一篇：從陣列創建最小堆-2種方法