0

这是代码。输出是一个非常接近正确排序的数组，但有几个元素乱序。任何人都能够发现错误？

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

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);

    }
}

}

4

2 回答 2

2

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

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

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

于 2013-05-03T05:21:02.400 回答
0

您必须在左侧列表中找到一个大于枢轴元素的值，并在右侧列表中找到一个小于枢轴元素的值，然后我们交换这些值。

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(10);
        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;
    }

    private static void quicksort(int low, int high) {
        int i = low, j = high;
        int pivot = u[low];
        while (i <= j) {
            while (u[i] < pivot) {
                i++;
            }
            while (u[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }
        }
        if (low < j) {
            quicksort(low, j); // note here
        }
        if (i < high) {
            quicksort(i, high); // note here
        }
    }

    private static void exchange(int i, int j) {
        int temp = u[i];
        u[i] = u[j];
        u[j] = temp;
    }
}
于 2013-05-03T04:47:21.220 回答