algorithm - Quicksort 分区前为什么将主元移动到数组的第一个或最后一个位置？

Question

我在一些地方看到，如果我们不选择第一个或最后一个元素作为基准，我们应该在分区开始之前先将它与第一个或最后一个位置交换。所以我尝试了一个例子，我使用这个算法得到了正确的分区 https://www.cs.auckland.ac.nz/software/AlgAnim/qsort1a.html
这种分区方法使用左指针和右指针。它将左指针移向中心，直到找到一个大于枢轴的元素。然后它将右指针移向中心，直到找到小于枢轴的元素。如果右指针 > 左指针。交换这两个位置的值。最后将枢轴放置在右指针的位置。
对于输入数组 12, 18, 17, 11, 13, 15, 16, 14，选择元素 15 作为基准。
这些是步骤:
12, 18, 17, 11, 13, 15, 16, 14

12、14、17、11、13、15、16、18(交换 18 和 14)

12、14、13、11、17、15、16、18(交换 17 和 13)

12、14、13、11、15、17、16、18(交换 15 和 17)

Answer 1

Hoare partition scheme在概念上与问题中的示例类似，除了可以从数组中的任何位置获取初始枢轴值，并且不执行特殊的最终情况交换，因为枢轴值和枢轴指针最终将位于其正确位置在霍尔分区期间。

这是一个快速排序的例子，它使用 3 的中位数、霍尔分区方案、排除与主元相邻且等于主元的元素(它们已经排序)，并且仅在较小的分区上使用递归来将最坏情况的堆栈空间限制为O(log(n)).

void QuickSort(uint32_t a[], size_t lo, size_t hi) {
    while(lo < hi){
        size_t i = lo, j = (lo+hi)/2, k = hi;
        uint32_t p;
        if (a[k] < a[i])            // median of 3
            std::swap(a[k], a[i]);
        if (a[j] < a[i])
            std::swap(a[j], a[i]);
        if (a[k] < a[j])
            std::swap(a[k], a[j]);
        p = a[j];
        i--;                        // Hoare partition
        k++;
        while (1) {
            while (a[++i] < p);
            while (a[--k] > p);
            if (i >= k)
                break;
            std::swap(a[i], a[k]);
        }
        i = k++;
        // at this point, a[i] or a[k] or both == p  (pivot value)
        while(i > lo && a[i] == p)  // exclude middle values == pivot
            i--;
        while(k < hi && a[k] == p)
            k++;
        // recurse on smaller part, loop on larger part
        if((i - lo) <= (hi - k)){
            QuickSort(a, lo, i);
            lo = k;
        } else {
            QuickSort(a, k, hi);
            hi = i;
        }
    }
}