-2

我正在尝试在 java 中实现几种不同类型的快速排序，但我的实现似乎都没有工作。我查看了整个互联网，我的代码看起来与我找到的所有代码非常相似，所以我不知道出了什么问题。我的代码如下：（请注意，这不完整，但我想如果我发现一个快速排序有什么问题，其他版本也可以）编辑：我遇到的问题是数组没有排序正确。我运行了一个名为 isSorted 的简单方法来告诉我数组是否正确排序。它适用于其他排序方法（插入排序、堆排序等），但在与我的快速排序实现一起使用时报告错误

public static void quickSort(int[] A) {
        flag=0;
        quickSortHelper(A, 0, A.length-1);
    }

public static void quickSortHelper(int [] A, int low, int high){
        if(low<high){
            if(flag==0){
            int q=DPartition(A, low,high,A[high]);
            quickSortHelper(A,low,q-1);
            quickSortHelper(A,q+1,high);
        }

public static int DPartition(int [] A, int low, int high,int pivot){
        int p=pivot;
        int i=low;
        int j=high-1;
        while (i<=j){
            while(i<=j && A[i]<=p){
                i=i+1;
            }
            while(j>=i && A[j]>=p){
                j=j-1;
            }
            if (i<j){
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            }

        }
      int temp = A[i];
      A[i] = A[p];
      A[p] = temp;
      return i;
    }
4

1 回答 1

3

该错误在您的DPartition方法中。在快速排序中，您向特定方向移动，一旦执行交换，您就会改变移动方向。但是，在上面的代码中，您在没有交换的情况下朝两个方向移动。

第一个 inner-while 循环找到了交换的位置，但不是交换，而是从下一个 inner-while 开始，它开始向相反的方向移动。那是错误的。

您应该再维护一个变量以将方向存储在数组中。

您可以尝试像这样修改您的代码（未测试）：-

// No need to pass `pivot` as parameter. Just use `high`.
public static int DPartition(int [] A, int low, int high) {  
    int i=low;
    int j=high;
    boolean leftToRight = false;
    boolean rightToLeft = true;

    while (i <= j) {   // Iterate till middle

        if (leftToRight) {  // Move left to right

            while(i <= j && A[i] <= A[j]){
                i=i+1;  // Move right until condition is satisfied
            }
            if (i < j) {   // If `i` has not moved beyond `j`. Perform Swap
                swap(i, j, A);   // Pass index for swapping along with array.
            }
            leftToRight = false;   // Toggle to change direction.
            rightToLeft = true;

        } else if (rightToLeft) {  // Move right to left.

            while(j >= i && A[j] >= A[i]){
                j=j-1;
            }
            if (j > i) {    // If j has not moved beyond `i`. Perform Swap
                swap(i, j, A);
            }
            rightToLeft = false;   // Toggle to change the direction
            leftToRight = true;
        } 
    }
    return i;   // Return `index` to split.
}

public static void swap(int p, int q, int[] a) {
    System.out.println("p = " + p + ", q = " + q);
    int temp = a[p];
    a[p] = a[q];
    a[q] = temp;
}
于 2012-11-30T05:38:55.233 回答