java - Java中的Quicksort-algorithm无法正确排序(第一个元素为数据透视)

This question already has answers here:

change pivot in my quickSort algorithm java
（3个答案）
Implementing Quicksort
（3个答案）
Quicksort. How to choose pivot element?
（6个答案）
QuickSort Algorithm what is next step once first pivot is located its final position in the array?
（4个答案）
我正在做一个任务，我们应该实现快速排序，以第一个元素为轴心我的代码中有一个小错误，导致列表元素（用于测试）排序错误。输出应该是1 3 7 8 9 10，但最终是1 7 3 8 9 10（7和3应该切换位置）我怀疑错误可能在第15-26行之间，但我似乎找不到，尽管许多人试图修复它。
有谁能看出什么不对劲吗？
（在第一个while循环中，我尝试使用i

public static void quickSort(int[] a, int lo, int hi) {
    if (!(hi > lo)) {
        return;
    }
    int pivot = a[lo];
    int i = lo;
    int j = hi + 1;
    int temp;
    i++;
    j--;
    while (i < j) {
        while (a[i] < pivot) {
            i++;
        }
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {
            switchPlace(a, i, j);
            i++;
            j--;
        }
    }
    switchPlace(a, lo, j);
    quickSort(a, lo, j - 1);
    quickSort(a, j + 1, hi);
}

public static void switchPlace(int[] a, int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

public static void printList(int[] a) {
    String res = "";
    for (int i = 0; i < a.length; i++) {
        res += a[i] + " ";
    }
    System.out.println(res);
}

public static void main(String[] args) {
    int[] a = { 9, 3, 10, 1, 8, 7 };
    quickSort(a, 0, a.length - 1);
    printList(a);
}

感谢您的帮助！

最佳答案

我将在这里描述一种调试此类算法的简单方法，包括：
对代码的较小部分应该产生什么样的期望；
验证这些期望是否得到满足。
第一点涉及到详细理解代码试图做什么，而第二点则意味着使用某种工具进行检查在这个特定的答案中举例说明的“工具”包括使用print消息，但通常它可以是其他的东西（例如步骤调试器）。
qsort算法的主要操作是交换轴周围的元素，以便较小的值在之前，较大的值在之后。
这一过程发生在lo和hi指数之间的各种子序列中。
现在让我们检查每个子序列的操作是否正确。
为此，我们可以显示初始子序列以及交换发生后的子序列，以便随后手动检查此操作是否正确执行。
在交换部分之前，我们可以使用如下代码：

    System.out.print("before: ");
    for (int k = lo; k <= hi; k++) {
        System.out.print(a[k] + ", ");
    }
    System.out.println();

在交换部分之后是这样的：

    System.out.print("after: ");
    for (int k = lo; k <= hi; k++) {
        System.out.print(a[k]);
        if (k == j) {
            System.out.print(" (pivot)");
        }
        System.out.print(", ");
    }
    System.out.println();
    System.out.println();

示例中序列的输出如下所示：
之前：9，3，10，1，8，7，
之后：8，3，7，1，9（枢轴），10
之前：8，3，7，1，
之后：1，3，7，8（枢轴）
之前：1，3，7，
之后：1（枢轴），3，7
之前：3，7，
之后：7，3（枢轴）
我们可以看到最后一个子序列发生了一个问题，长度为2。
好处是我们现在只能专注于这种情况，准确地了解发生了什么。
例如，我们甚至可以直接传递到算法int[] a = {3, 7};。
仔细考虑了在这种情况下发生的情况，我们可以看到问题在于，j索引没有跳过比枢轴大的元素，因为while (i < j)在这种情况下立即退出（我们从一开始就有i=＝j）。有多种解决方案，其中一种似乎有效的方法是在各自的条件下使用while (i <= j)——尽管您明确提到它可能导致无限循环，但事实上似乎并非如此。
下面是包含此修复程序的代码（以及上面描述的其他prints）：

public static void quickSort(int[] a, int lo, int hi) {
    if (!(hi > lo)) {
        return;
    }
    int pivot = a[lo];
    int i = lo;
    int j = hi + 1;
    int temp;
    i++;
    j--;

    System.out.print("before: ");
    for (int k = lo; k <= hi; k++) {
        System.out.print(a[k] + ", ");
    }
    System.out.println();

    while (i <= j) {
        while (a[i] < pivot) {
            i++;
        }
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {
            switchPlace(a, i, j);
            i++;
            j--;
        }
    }
    switchPlace(a, lo, j);

    System.out.print("after: ");
    for (int k = lo; k <= hi; k++) {
        System.out.print(a[k]);
        if (k == j) {
            System.out.print(" (pivot)");
        }
        System.out.print(", ");
    }
    System.out.println();
    System.out.println();

    quickSort(a, lo, j - 1);
    quickSort(a, j + 1, hi);
}

public static void switchPlace(int[] a, int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

public static void printList(int[] a) {
    String res = "";
    for (int i = 0; i < a.length; i++) {
        res += a[i] + " ";
    }
    System.out.println(res);
}

public static void main(String[] args) {
    //int[] a = {3, 7};
    //int[] a = { 9, 3, 10, 1, 8, 7 };
    int[] a = {24, 2 , 45 ,20 ,56 ,75 ,2 ,56 ,99 ,53 ,12};
    quickSort(a, 0, a.length - 1);
    printList(a);
}

关于java - Java中的Quicksort-algorithm无法正确排序(第一个元素为数据透视)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46389674/