我正在尝试在 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

OutputShown

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。您的代码在其签名中声明了它，但从不使用它。

Answer 2

这是我想出的代码。这里我取最右边的值作为枢轴值，继续往前。通过递归进一步进行。希望你能理解。

 public class QuickSortDemo {
    public static void main(String[] args) {
    int[] input = {6, 3, 2, 5, 4};
    int[] output = quickSort(input, 0, input.length-1);
    for(int a : output) {
    System.out.println(a);
    }}
    public static int[] quickSort(int[] array, int lowerIndex, int higherIndex) {

     int i = lowerIndex;
     int j = higherIndex;
     // calculate pivot number, rightmost value
     int pivot = array[higherIndex];
     // Divide into two arrays
     while (i <= j) {
     while (array[i] < pivot) {
     i++;
     }
     while (array[j] > pivot) {
     j--;
     }
     if (i <= j) {
     int temp = array[i];
     array[i] = array[j];
     array[j] = temp;
     //move index to next position on both sides
     i++;
     j--;
     }
     }
     // call quickSort() method recursively
     if (lowerIndex < j)
     quickSort(array,lowerIndex, j);
     if (i < higherIndex)
     quickSort(array, i, higherIndex);

     return array;
     }
    }

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

I am trying to implement QuickSort in java but Could not get output?

java

quicksort