我正在做一个算法类项目，在该项目中，我们必须通过建议的改进来修改QuickSort的实现。这些建议之一如下：不要单挑数组中的枢轴，避免最后一次交换分区方法。
我很难确切了解他的意思。没有枢轴，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 - QuickSort算法改进，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12849309/