快速排序.如何选择枢轴元素？

Question

我读了关于quicksort算法,我不明白如何选择枢轴元素.从教程我得到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)运行时间.所以选择中间元素总是更好.

Answer 2

假设left=3和right=9再right-left/2 = 3不是中间,但它6是= left + (right - left) / 2.(只是添加了基础值left).

感谢@ Dukeling:
你可以简单地写 一下(left + right) / 2.

    left + (right-left)/2 
=>  2*left/2 + (right-left)/2    //multiply (left * 2/2)
=>  (2*left + right-left)/2 
=>  (left + right)/2