java - 快速排序算法改进

Question

我正在做一个算法类项目，其中我们必须使用建议的改进来修改 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()

Answer 1

我不会尝试为您实现它，但我对这个建议的“改进”的解释是，他希望您仍然选择一个主元值并根据它们位于该值的哪一侧，但不特殊对待包含该值的数组条目。

这应该不难做到，但它根本不会提高算法的性能，而且我怀疑这在任何其他意义上都有很大的改进。