java - 在 Java 中解决我的快速排序算法的问题？

Question

在对 quicksort 的方法进行故障排除时算法，弹出这个问题；

考虑这个单独打印数组元素的简单示例:

public static void print1(int[] arr, int start, int end){
        for (int k = start; k<end;k++){
            System.out.println(arr[k]);
        }
    }
    public static void print2(int[] arr, int start, int end){
        for (int k=start; k<=end;k++){
            System.out.println(arr[k]);
        }
    }

主要是，如果我调用:

public static void main(String[] args) {
        int[] data2 = new int[]{10,11,9,7,5};
       print1(data2,0,data2.length);
       System.out.println("___________");
       print2(data2,0,data2.length-1);
    }

两者都打印相同的内容，这很好；(请注意，我将 data2.length 和 data2.length-1 作为我的 print1 和 print2 方法的参数传递，并且每个方法中的 for-loop 会相应更改)

现在出现了快速排序机制的问题:考虑这段代码:

public static void quickSort2(int[] arr, int i, int j){
        if (i<j){
            int part =partition(arr, i, j);
            quickSort2(arr, i, part-1);
            quickSort2(arr, part+1, j); 
        }
    }

public static int partition(int[] arr, int start, int end){
        int pivot = arr[start];
        int i = start;
        for (int j = start+1;j<=end;j++){ // ******
            if (arr[j]<pivot){
                    i++;
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
            }
        }
        arr[start]=arr[i];
        arr[i]=pivot;
        return i;
    }

主要是；

public static void main(String[] args) {
       //int[] data = new int[]{5,10,1,9,4,4,8,3,6,2,7,4};
        int[] data = new int[]{3,4,1,2};
        int[] data2 = new int[]{10,11,9,7,5};
       System.out.print("Unsorted array data ");
       display(data);
       System.out.print("\nUnsorted array data2 :");
       display(data2);
       quickSort2(data, 0, data.length-1);
       System.out.println("_____________");
       quickSort2(data2,0,data2.length-1);
       System.out.print("\nSorted array data: ");
       display(data);
       System.out.print("\nSorted array data2:");
       display(data2);
}

运行良好；现在，如果我将调用更改为 quickSort(data, 0, data.length)并更改 for-loop行(在代码中用 ******* 标记)到 for (int j = start+1;j<end;j++) ，我得到完全不同的结果:即:前两个元素未排序，但其余元素已排序。我明白了

Sorted array data: [2, 1, 3, 4]

Sorted array data2:[5, 9, 7, 10, 11]

我需要一些帮助

Answer 1

在快速排序函数中调用第一个分区时，您还必须更改:

quickSort2(arr, i, part-1);

到

quickSort2(arr, i, part);

这是因为您没有使用最后一个索引(结束)。因此，您的快速排序将是不完整的，因为您没有将最后一个元素放在基准之前，即使它的值低于基准。