我阅读了快速排序算法,但我不明白如何选择主元。从教程中我得到了 quciksort 的示例代码:
public void quicksort(int[] A, int left, int right) {
int pivot = A[left + (right - left) / 2];
int i = left;
int j = right;
while (i <= j) {
while (A[i] < pivot) {
i++;
}
while (A[j] > pivot) {
j--;
}
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
if(left < j)
quicksort(A,left,j);
if(i < right)
quicksort(A,i,right);
}
但为什么我们选择使用这个 A[left + (right - left)/2];
的枢轴?
为什么不是 A[(right - left)/2]
最佳答案
考虑 left=6, right=10
,然后 (right-left)/2
是 2。您选择的元素不在您的范围内子数组?
您可以选择 6 到 10 之间的任何元素作为快速排序。但是如果您选择第一个或最后一个元素并且如果数组已排序,那么您的算法可能会运行 O(n^2) 时间。所以选择中间元素总是更好。
关于java - 快速排序。如何选择枢轴元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17442139/