我正在做一个算法类项目,其中我们必须使用建议的改进来修改 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()
最佳答案
我不会尝试为您实现它,但我对这个建议的“改进”的解释是,他希望您仍然选择一个主元值并根据它们位于该值的哪一侧,但不特殊对待包含该值的数组条目。
这应该不难做到,但它根本不会提高算法的性能,而且我怀疑这在任何其他意义上都有很大的改进。
关于java - 快速排序算法改进,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12849309/