Hoare的quicksort是如何工作的，即使partition（）之后的枢轴的最终位置不是它在排序数组中的位置？

Question

所有变量名都来自QuickSort的维基百科页面的Lomuto和Hoare的QuickSorts伪代码。

如果p是partition函数返回的内容，则Hoare将他的数组从lo划分为p并从p+1划分为hi；而Lomuto将他的数组从lo划分为p-1并从p+1划分为hi。

我可能错了，但QuickSort的理念是...

1. 在子数组（透视）中取一个元素。
2. 重新排列子数组，使枢轴左侧的所有元素小于枢轴，而枢轴右侧的所有元素大于枢轴。
3. 围绕枢轴划分数组。对两个较小的子数组重复此过程。继续这样做，直到遇到只有一个或更少元素的数组，因为该数组已经排序。

我发现Hoare的partition比Lomuto的更容易理解。霍尔的划分只是简单地指示我们从左端和右端开始，并且不断地朝对方移动。如果左标记遇到大于枢轴的元素，则左标记暂停，等待右标记找到小于枢轴的元素。然后他们交换元素，这样左边的标记有较小的元素，右边的标记有较大的元素。他们一直这样做直到他们见面。非常直截了当。

Lomuto的partition可以看作是一条蛇，有两个部分，一个头和一条尾。枢轴是固定的（我通常把最后一个元素作为Lomuto的枢轴）。蛇从左侧开始，在最后一个元素之前停止。当蛇遇到一个比枢轴小的元素时，这个元素就会移到尾巴上，尾巴的长度就会增加。当发现一个大于枢轴的元素时，该元素就会到达蛇的头部。最后，枢轴放在尾部和头部之间。它非常清晰，但不像Hoare的partition那样直观或高效（在某些情况下）。

令我困惑的是，Hoare的分区并不能确保partition运行完成后的枢轴位置是它在最终排序数组中的位置。在Hoare的分区中，我能识别的唯一模式是I位于枢轴的最后位置，而j是I或i-1，j和I是左右标记。

然而，洛穆托的分治保证了这一点。因此，当我退一步来看看更大的画面时，Lomuto将数组从lo划分为p-1以及从p+1划分为hi是有意义的。但是，我无法理解Hoare如何将他的数组从lo划分为p以及从p+1划分为hi来弥补他的分区没有将其枢轴放入正确的位置。

Answer 1

我自己也在通过Hoare的QuickSort查看例子和排序数组。我想我在Hoare的Algo分区中发现了另一个有趣的模式。这也许可以解释为什么Hoare的方法行得通。洛穆托将阵分为三部分；比枢轴小的元素，比枢轴大的元素。我认为Hoare看待事物的方式不同。他把阵分成两部分；小于枢轴的元素，等于或大于枢轴的元素。我陷入的一个陷阱是，Lomuto的分区返回的是枢轴的最终位置，而Hoare的分区返回的是刚好在枢轴的最终位置之前的位置。这就是为什么Lomuto会从LO快速排序到P-1，而Hoare会从LO快速排序到P。可以得出的另一个推论是，如果Hoare的分区返回i而不是j，那么我们将把数组分成两部分--从lo到i-1和从i+1到hi，就像Lomuto所做的那样。我只用了4个小时就明白了。