java - 快速排序未正确排序

Question

我基本上是从加州大学伯克利分校的快速排序视频中复制了我的代码，但它似乎几乎只能成对排序。我不确定这里发生了什么。

我已经多次查看每一行，但看不出有什么问题。一切对我来说都很有意义。

static <E extends Comparable<? super E>>
void quicksort(E[] A, int low, int high) {
    if (low < high) {
        int pivotIndex = (low + high) / 2;
        E pivot = A[pivotIndex];
        // move pivot to end
        A[pivotIndex] = A[high];
        A[high] = pivot;

        int i = low - 1;
        int j = high;
        do {
            do {
                i++;
            } while (A[i].compareTo(pivot) < 0);
            do {
                j--;
            } while ((A[i].compareTo(pivot)) > 0 && (j > low));
            if (i < j) {
                E swap = A[i];
                A[i] = A[j];
                A[j] = swap;
            }
        } while (i < j);
        // i is now the first spot in the right partition (where we will put pivot)
        // now put pivot back where it belongs
        A[high] = A[i];
        A[i] = pivot;
        quicksort(A, low, i - 1); // sort left partition
        quicksort(A, i + 1, high);
    }
}

我期望[2, 3, 5, 6, 10, 101, 200, 300]，但得到[3, 5, 2, 6, 10, 101, 200, 300]

Answer 1

第二个内部循环中的比较使用 A[i] 进行比较，而它应该使用 A[j]:

            } while ((A[j].compareTo(pivot)) > 0 && (j > low));  // A[j] not A[i]

<小时/>

这种类型的快速排序的另一种变体不会将主元与 A[high] 交换，并且通过将主元留在中间，代码不需要在第二个内部循环中检查 j > low，这有点快。使用此变体需要进行其他更改:将 j 初始化为 high + 1，并且两个递归调用应该是 fastsort(A, low, j) 和 fastsort(A, j+1, high)。请注意，等于主元的值(包括主元本身)可能最终出现在任一分区中，因为等于主元的值会被交换。

基元 (int) 的示例代码，在较小或相等的部分上使用递归，然后迭代返回较大的部分，以避免最坏情况下的堆栈溢出。它可以转换为使用通用对象E。

    public static void qsort(int[] a, int lo, int hi)
    {
        while(lo < hi){
            int  md = lo+(hi-lo)/2;
            int  ll = lo-1;
            int  hh = hi+1;
            int p = a[md];
            int t;
            while(true){
                while(a[++ll] < p);
                while(a[--hh] > p);
                if(ll >= hh)
                    break;
                t     = a[ll];
                a[ll] = a[hh];
                a[hh] = t;
            }
            ll = hh++;
            if((ll - lo) <= (hi - hh)){
                qsort(a, lo, ll);
                lo = hh;
            } else {
                qsort(a, hh, hi);
                hi = ll;
            }
        }
    }