1

我正在做一个算法类项目，我们必须在其中修改 QuickSort 的实现并提出改进建议。其中一个建议如下：不要单挑数组中的pivot，避免分区方法的最后一次swap。

我很难理解他的意思。没有枢轴，它怎么还是 QuickSort？任何洞察这可能意味着什么将不胜感激。这是要修改的Java 代码。

public void quickSort() {
    recQuickSort(0, nElems - 1);
}

public void recQuickSort(int left, int right) {
    if (left >= right)
        return;
    long pivot = a[right];
    int mid = partition(left, right, pivot);
    recQuickSort(left, mid - 1);
    recQuickSort(mid + 1, right);
} // end recQuickSort()

public void swap(int dex1, int dex2) { // swap two elements
    long temp = a[dex1]; // A into temp
    a[dex1] = a[dex2]; // B into A
    a[dex2] = temp; // temp into B
} // end swap()

public int partition(int left, int right, long pivot) {
    // assuming pivot == a[right]
    int leftPtr = left - 1; // left of the first element
    int rightPtr = right; // position of pivot
    while (true) {
        while (a[++leftPtr] < pivot)
            ; // find bigger
        while (leftPtr < rightPtr && a[--rightPtr] >= pivot)
            ; // find smaller
        if (leftPtr >= rightPtr) // if pointers cross,
            break; // partition done
        else
            // not crossed, so
            swap(leftPtr, rightPtr); // swap elements
    } // end while(true)
    swap(leftPtr, right); // restore pivot
    return leftPtr; // return pivot location
} // end partition()
4

2 回答 2

0

I'm not going to try to implement it for you, but my interpretation of this suggested "improvement" is that he wants you to still choose a pivot value and partition the array into sections according to which side of that value they're on, but not treat the array entry containing that value specially.

It shouldn't be hard to do, but it won't improve performance of the algorithm at all, and I doubt that it's much of an improvement in any other sense.

于 2012-10-11T22:26:34.083 回答
0

看起来他不希望您以数组中的实际元素为中心。该partition()方法中最后一次交换的要点是他将枢轴移动到数组中的正确位置（请注意，他在partition()调用后从不移动枢轴元素）。

编辑如果您对“不使用枢轴”感到困惑，那么您仍在使用枢轴......它只是不是数组中的枢轴。想象一下手动进行快速排序，您可以选择任意值进行旋转。

问题是这种交换根本不会对性能产生负面影响。另一方面，这应该是一个快速的变化......

于 2012-10-11T22:30:21.347 回答