Hoare分区算法能否围绕指定枢轴？代码修改与原理疑问

分区算法的异常表现 #

我在学习快速排序测试随机枢轴时，发现讲师教授的分区算法存在异常表现。该算法是Hoare分区算法的修改版本：选取首个元素作为枢轴，最终将其与右指针（j位置）的值交换。而标准Hoare算法的表现更为特殊。

我发现它并非一定会围绕选定的枢轴进行分区，而是可能围绕完全不同的元素。例如数组{2,1,4,6,9,5,3,7}，若选取6作为枢轴，算法最终会围绕5分区，得到{2,1,4,3,5,9,6,7}，此时无法从函数返回单个枢轴值，只能调用Quicksort(a,lo,j)和Quicksort(a,i,hi)，这意味着后续调用会包含枢轴。

现有可行代码及修改需求 #

以下是我从@rcgldr处获取的适用于随机枢轴的可行代码：

void QuickSort(int *a, int low, int high)
{
    int i, j;
    int p, t;
    if(low >= high)
        return;
    p = a[(low+high)/2] ;
    i = low;
    j = high;
    while (i <= j){
        while (a[i] < p )i++;
        while (a[j] > p )j--;
            if (i > j)
                break;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
    }
    QuickSort(a, low, j);
    QuickSort(a, i, high);
}

我能否修改上述代码，使其围绕枢轴的索引进行分区，且后续调用不包含枢轴？通常它会围绕j位置元素分区，但当枢轴为最大元素时，会围绕i位置元素分区（例如数组{80,73,48,90,33,53,60}中，若90为枢轴，最终i会指向90）。这是因为我想要实现该分区方案的迭代版快速排序，需要将枢轴存入栈中。虽然可以随机选取枢轴并与首个元素交换，但这似乎是在回避问题。

Hoare算法分区逻辑的困惑 #

此外，我无法理解Hoare算法的分区逻辑，尤其是那些分区结果完全不可预测的情况（例如修改后的数组{53,80,73,48,90,33,60,110,70}，它甚至不会围绕任何枢轴分区），希望能得到相关原理解析。

内容的提问来源于stack exchange，提问作者MkB