使用 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]

显然，它没有正确排序，我一直在一遍又一遍地思考，但仍然不知道我的算法的哪一部分是错误的......

java 算法输出 quicksort 分区

在的第一次递归调用中，应包含透视绑定，而不是传递。quicksortpivot-1
在您的方法中，您忘记移动索引并在交换后移动索引。HoarePartitionij
返回条件不仅应检查两个索引是否相交，还应检查它们是否相互交叉ijif (i >= j) return j;
最里面的循环应该写成两个循环，而不是 a 和 awhilewhiledo-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]

    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()

上一个：Jupyter_notebook无法导入我刚刚安装的 nltk

下一个：后缀评估计算结果错误

使用 HoarePartition 的快速排序得到不正确的输出

Quicksort using HoarePartition got incorrect output

评论

输出

评论