java 中的递归快速排序不起作用

Question

我正在尝试在 java 中实现快速排序，它以数组的最后一个元素为基准。然而，它似乎并没有工作，即使在纸面上它应该..

这是输出：

before sort: 5 2 3 1 4 

after sort: 3 2 4 5 1

预期的输出是 1,2,3,4,5，但这似乎并没有发生。

public static void main(String[] args) {
    int A[] = {5,2,3,1,0};
    ArrayUtils.printArray("before sort", A);
    quick_sort(A, 0, A.length-1);
    ArrayUtils.printArray("after sort", A);
}

public static void quick_sort(int[] A, int p, int r) {
    if (p < r) {
        int q = partition(A, p, r);
        quick_sort(A, p, q-1);
        quick_sort(A, q+1, r);
    }
}

我已经追踪到问题出在调试器的分区中，但我似乎无法找到它的位置。似乎for循环有时会产生错误的i，但有时它会正常工作..我不确定，这就是我问的原因。

public static int partition(int A[], int p, int r) {
    int x = A[r];
    int i = p-1;
    for(int j = p; j < r-1; j++) {
        if (A[j] <= x) {
            i = i + 1;
            int temp = A[j];
            A[j] = A[i];
            A[i] = temp;
        }
    }
    int temp = A[r];
    A[r] = A[i + 1];
    A[i + 1] = temp;
    return i + 1;
}

其中 printArray() 是

public static void printArray(String name, int[] array) {
    if (array.length >= 10) {
        System.out.print(name + ": \n");
    } else {
        System.out.print(name + ": ");
    }

    for(int i = 0; i < array.length; i++) {
        if (i % 10 == 0 && i > 0) {
            System.out.print("\n");
        }
        System.out.print(array[i] + " ");

    }
    System.out.println("\n");
}

Answer 1

您的分区算法看起来是基于 Wikipedia 中的 Lomuto 分区方案。然而，在维基百科中，伪代码表示 for j := lo to hi - 1，它基于 Pascal 语法。在类 Pascal 语言中，这意味着 j 的最后一个值是 hi - 1。在类似 C 的语言中，例如 Java，我们通常将索引的最后一个值之后的值设置为上限，而不是最后一个值。这意味着在您的代码中，j 实际上永远不会具有值 hi - 1。修复 for 循环以确保 j 确实采用值 r-1 让事情正常进行，以你的例子为例。

java 中的递归快速排序不起作用

Recursive QuickSort in java not working

java

algorithm

recursion

quicksort

partition