java - 我正在尝试在 java 中实现 QuickSort 但无法获得输出？

Question

我正在尝试通过将最后一个元素作为枢轴来实现快速排序。但我无法产生有效的输出。

还需要进行哪些更改才能使其随机化？我正在用 Java 编码。

public class QuickSortDemo {
    public static void quicksort(int A[], int temp[], int left, int right) {
        int q, i;

        //why u need to check this  base case always
        if (left < right) {
            q = partition(A, temp, left, right);
            quicksort(A, temp, left, q - 1);
            quicksort(A, temp, q + 1, right);

            for (i = 0; i < A.length; i++) {
                System.out.println(A[i]);
            }
        }
    }

    public static int partition(int A[], int temp[], int left, int right) {
        int x, i, j;

        x = A[right];
        i = left - 1;

        for (j = left; j <= right - 1; j++) {
            if (A[j] <= x) {
                i = i + 1;
                A[i] = A[j];
            }
        }

        A[i + 1] = A[right];
        return i + 1;
    }

    public static void main(String s[]) {
        int ar[] = {6, 3, 2, 5, 4};
        int p[] = new int[ar.length];
        quicksort(ar, p, 0, ar.length - 1);
    }
} //end class QuickSortDemo

输出显示

2

2

4

5

4

2

2

4

4

4

2

2

4

4

4

Answer 1

正如评论中提到的，分区方法存在一些错误。在实现快速排序时，您希望交换数组中的元素，而不仅仅是覆盖前面的元素。他们会迷路的。

此外，代码从左侧开始，并且始终交换小于或等于主元的每个元素。如果元素已经位于数组的正确部分，则这些操作是不必要的。

最好从左侧搜索大于主元的元素。然后，从右侧搜索小于主元的元素，仅交换这些元素，然后继续，直到所有必要的元素都被交换。

标准实现(据我所知)看起来像这样

public static int partition(int A[], int left, int right) {
    int pivot, i, j;

    pivot = A[right];
    i = left;
    j = right - 1;

    do {
        // Search for element greater than pivot from left, remember position
        while ( A[i] <= pivot && i < right ) i++;

        // Search for element less than pivot from right, remember positon
        while ( A[j] >= pivot && j > left ) j--;

        // If elements are in the wrong part of the array => swap
        if ( i < j ) swap( A, i, j );

    // Continue until the whole (sub)array has been checked    
    } while ( j > i );

    // Put the pivot element at its final position if possible
    if ( A[i] > pivot )
        swap ( A, i, right );

    // Return the border / position of the pivot element    
    return i;
}

交换一切如常

public static void swap(int[] A, int first, int second) {
    int temp = A[first];
    A[first] = A[second];
    A[second] = temp;
}

另请注意，在此代码中无需使用 temp。您的代码在其签名中声明了它，但从未使用它。