0

对于课程作业，我的任务是实现一个基本的快速排序算法。我已经实现了我认为可以工作的快速排序，但是它不适用于我们必须测试的特定数组。这个数组应该是最坏的情况，应该进行更多的比较是可以理解的，但在这种情况下我根本无法让它产生一个排序的数组。

伪代码：

开始快速排序

如果 (R > L) 那么

p := 分区(A,L,R);

快速排序（A，L，p-1）；

快速排序(A,p+1,R);

菲

结尾

开始分区

v := A[右]

pL := 左; pR := 右-1；

而 (pL < pR) 做

而 (A[pL] < v) 做 pL:=pL+1 od 而 (A[pR]>=v 和 pR>left) 做

pR:=pR-1

口

如果 (pL < pR) 那么

交换(A,pL,pR)

菲

口

交换（A，PL，右）；

返回 pL;

有问题的代码：

public void quickSort(int[] A, int L, int R) {
    if (L < R) {
        int p = partition(A, L, R);
        quickSort(A, L, p - 1);
        quickSort(A, p + 1, R);
    }
}
private int partition(int[] A, int left, int right) {
    int pivot = A[right];
    int pointerLeft = left;
    int pointerRight = right - 1;
    while (pointerLeft < pointerRight) {
        while (A[pointerLeft] < pivot) {
            pointerLeft = pointerLeft + 1;
            compQS++;
        }
        while (A[pointerRight] > pivot && pointerRight > left) {
            pointerRight = pointerRight - 1;
            compQS++;
        }
        if (pointerLeft < pointerRight) {
            swap(A, pointerLeft, pointerRight);
        }
    }
    swap(A, pointerLeft, right);
    return pointerLeft;

}

private void swap(int[] A, int i, int j) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

有问题的数组：

1 3 41 5 6 9 11 20 21 22 23 24 26 28 29 30 33 39 41 41 43 45 46 2 54 55 55 56 57 60 61 63 65 66 67 69 69 70 71 180 75 1 74 86 8 7 75 74 86 7 91 92 92 94 94 94 99 101 101 101 101 103 105 106 107 110 110 110 110 113 115 115 118 125 127 127 128 129 136 136 80 143 143 144 144 144 147 147 148 148 148 152 152 153 153 153 155 155 156 158 158 158 158 158 158 169 170 175 175 175 175 176 176 178 184 185 189 190 193 194 193 195 194 193 195

任何指导将不胜感激。我不禁认为这与重复有关，但看不出我的实现哪里出错了。

4

2 回答 2

1

查看代码，有两点看起来很可疑：

在递归中，你写

   quickSort(A, L, p - 1);
   quickSort(A, p + 1, R);

任何一个都应该是 p，否则你会错过中间元素。

另一条看起来很奇怪的线是

swap(A, pointerLeft, right);

我认为如果右（即枢轴）是左右之间的最大值，这会造成麻烦。考虑一下，我认为当枢轴是极值（集合中的最小或最大）时，问题出在您的分区代码中。这与给定数组是一个非常糟糕的情况的陈述相吻合。

于 2013-10-27T20:19:42.400 回答
0

我在您的代码中看到两个可能的问题：

1）当您第一次调用 quickSort 时，您缺少中间值（您使用 p-1 作为第一次调用的右表达式，使用 p+1 作为第二次调用的左表达式，p 会发生什么？）

2）你正在交换pointerLeft与right

试试这个：

quicksort(A,L,p);
quicksort(A,p+1,R);

和

swap(A,pointerLeft,pointerRight);

试试看！

于 2013-10-27T20:23:57.727 回答