为快速排序选择枢轴

Question

我找到了代码。但我不明白它是如何工作的。据我所知 pivot - 它是数组的中间元素。但是这里的枢轴是 int pivot = quickSortArray[p]，其中 int i = p，所以 p = 0 和 0 它不是数组的中间，可以解释一下吗？

 public int partition(int p, int q) {
    int i = p;
    int j = q + 1;
    // Get the pivot element from the middle of the list
    int pivot = quickSortArray[p];
    // Divide into two lists
    do {
        // If the current value from the left list is smaller then the pivot
        // element then get the next element from the left list
        do {
            i++;// As we not get we can increase i
        } while (quickSortArray[i] < pivot && i<q);
        // If the current value from the right list is larger then the pivot
        // element then get the next element from the right list
        do {
            j--;// As we not get we can increase j
        } while (quickSortArray[j] > pivot);
        // If we have found a values in the left list which is larger then
        // the pivot element and if we have found a value in the right list
        // which is smaller then the pivot element then we exchange the
        // values.
        if (i < j) {
            swap(i, j);
        }

    } while (i < j);
    // swap the pivot element and j th element
    swap(p, j);
    quickSortComparisons++;
    return j;

}

private void swap(int p, int j) {
    // exchange the elements
    int temp = quickSortArray[p];
    quickSortArray[p] = quickSortArray[j];
    quickSortArray[j] = temp;
    quickSortSwaps++;
}

public void quicksort() {
    // Recursion
    quicksort(0, quickSortCounter - 1);
}

public void quicksort(int p, int q) {
    int j;
    if (p < q) {
        // Divide into two lists
        j = partition(p, q);
        // Recursion
        quicksort(p, j - 1);
        quicksort(j + 1, q);
    }
    quickSortComparisons++;
}

Answer 1

枢轴不必是中间元素。它必须是一个随机元素。代码将枢轴固定为始终是第一个元素，这可能会使代码更容易。这不是最优的，因为如果你有一个降序排序的数组，它将需要 O(n^2) 而不是 O(n log n)。最优的是随机选择一个元素。

为快速排序选择枢轴

Choosing the pivot for a QuickSort

java

pivot

quicksort