java - 快速排序。如何选择枢轴元素？

Question

我阅读了快速排序算法，但我不明白如何选择主元。从教程中我得到了 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]

Answer 1

考虑 left=6, right=10，然后 (right-left)/2 是 2。您选择的元素不在您的范围内子数组？

您可以选择 6 到 10 之间的任何元素作为快速排序。但是如果您选择第一个或最后一个元素并且如果数组已排序，那么您的算法可能会运行 O(n^2) 时间。所以选择中间元素总是更好。