java - 快速排序:几乎排序，但不完全排序。怎么了？

Question

这是代码。输出是一个几乎正确排序的数组，但有几个元素乱序。有人能发现错误吗？

我很确定交换和快速排序方法是正确的，但为了以防万一，我在这里发布了所有方法。

package quicksort;
import java.util.Random;
import java.util.Arrays;

public class QuickSort {

/**
 * @param args the command line arguments
 */

private static int[] u;

public static void main(String[] args) {

    u = makeArray(100);
    System.out.println(Arrays.toString(u));

    quicksort(0, u.length - 1);
    System.out.println(Arrays.toString(u));

}

public static int[] makeArray(int n) {

    int[] a = new int[n];
    int j;
    Random r = new Random();

    for (int i = 0; i < n; i++) {
        j = (r.nextInt(100) + 1);
        a[i] = j;
    }

    return a;
}

public static int partition(int left, int right, int pivot) {

    int p = pivot;    // pivot
    int lPt = left - 1;
    int rPt = right + 1;

    while (true) {

        while ((lPt < right) && (u[++lPt] < p));

        while ((rPt > left) && (u[--rPt] > p));

        if (lPt >= rPt) {
            break;
        } else {

            swap(lPt, rPt);
            System.out.println("Swapping " + lPt + " " + rPt);

        }


    }

    return lPt;
}

public static void swap (int a, int b) {        
    int temp = u[a];
    u[a] = u[b];
    u[b] = temp;
}

public static void quicksort(int l, int r) {

    if (r - l <= 0) {
        return;

    } else {

        int part = partition(l, r, u[l]);

        quicksort (l, part - 1);
        quicksort (part + 1, r);

    }
}

}

Answer 1

问题出在分区方法上。在交换结束时，枢轴元素未放置在正确的位置。我更改了方法签名，以便您传递枢轴元素的位置，而不是枢轴的值，因此在 fastsort() 中您现在可以编写:

int part = partition(l, r, l);

在枢轴方法的主体中，我将枢轴元素交换到该部分的末尾(通过与右侧交换)。为了让我们在交换时忽略这个元素，我在 rPT 初始化时去掉了“+ 1”。然后，我在 while 循环之后添加了一条语句，以将枢轴元素移动到位。经过这三个更改，该方法现在如下所示:

public static int partition(int left, int right, int pivotPosition) {

    int p = u[pivotPosition];    // pivot

    // Move pivot to the end
    swap(pivotPosition, right);

    int lPt = left - 1;
    int rPt = right;

    while (true) {

        while ((lPt < right) && (u[++lPt] < p));

        while ((rPt > left) && (u[--rPt] > p));

        if (lPt >= rPt) {
            break;
        } else {

            swap(lPt, rPt);
            System.out.println("Swapping " + lPt + " " + rPt);
        }

    }

    // Put pivot in its place
    swap(lPt, right);

    return lPt;
}

通过这些更改，代码对我有用。