java - 用 Java 实现维基百科就地快速排序伪代码

Question

我在 https://en.wikipedia.org/wiki/Quicksort 上使用名为 Lomuto 分区方案的伪代码。但我只是不明白我在这里做错了什么。该数组永远不会被组织起来(无论输入大小如何)。这是我为期末考试做的准备。我的教授希望我们使用这个算法，但我不能只是学习它，除非我通过测试了解它是如何工作的。

private static void quickSort(Integer A[], int l, int r) {

    if (l < r) {
        int k = partition(A, l, r);
        quickSort(A, l, k - 1);
        quickSort(A, k + 1, r);
    }
}

private static int partition(Integer A[], int l, int r) {
    int pivot = A[r];
    int i = l;

    for (int j = l; j <= r - 1; j++) {
        if (A[j] <= pivot) {
            i++;
            int temp = A[j];
            A[j] = pivot;
            pivot = temp;
        }
    }

    int temp = A[i + 1];
    A[i + 1] = A[r];
    A[r] = temp;

    return i + 1;
}

Answer 1

除了你没有正确转录伪代码之外，我不知道还能说什么。在 partition 的开头，i 应等于 l - 1，但您将其设置为 l。

此外，您不会在嵌套循环中将 A[i] 与 A[j] 交换。这是正确的实现:

private static int partition(Integer A[], int l, int r) {
    int pivot = A[r];
    int i = l - 1;

    for (int j = l; j <= r - 1; j++) {
        if (A[j] < pivot) {
            i++;
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }

    int temp = A[i + 1];
    A[i + 1] = A[r];
    A[r] = temp;

    return i + 1;
}