java - 用Java实现Wikipedia就地快速排序伪代码

我在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;
}

最佳答案

除了您没有正确转录伪代码外，我不知道还有什么要说的。在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;
}