sorting - Hoare 的快速排序如何工作，即使在 partition() 之后枢轴的最终位置不是它在排序数组中的位置？

Question

所有变量名均来自Quicksort's wikipedia page Lomuto 和 Hoare 的快速排序伪代码。

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

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

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

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

Lomuto 的分区，可以看作是一条蛇，由头和尾两部分组成。枢轴是固定的(我通常将最后一个元素作为 Lomuto 的枢轴)。蛇从左侧开始，并在最后一个元素之前停止。当蛇遇到一个小于枢轴的元素时，该元素会移动到尾部并且尾部的长度会增加。当发现大于枢轴的元素时，该元素将转到蛇的头部。最后，枢轴位于尾部和头部之间。它非常清晰，但不如 Hoare 的分区 直观或高效(在某些情况下)。

让我感到困惑的是，Hoare 的分区不能确保在 partition 完成其过程后枢轴的位置将是它在最终排序数组中的位置。在 Hoare 的分区中，我唯一能识别的模式是 i 位于枢轴的final position 并且 j 是 i 或 i-1，j 和 i 是左右标记。

然而，Lomuto 的分区保证了这一点。所以，当我退一步看大局时，Lomuto 将数组从 lo 划分为 p-1 并从 p+1 划分是有意义的 到 hi。但是，我无法理解 Hoare 如何将他的数组从 lo 划分为 p 以及从 p+1 划分为 嗨，弥补他的分区没有将其枢轴放在正确的位置。

Answer 1

我一直在研究示例并自己通过 Hoare 的快速排序对数组进行排序。我想我在 Hoare 的分区算法中发现了另一个有趣的模式。这可以解释为什么 Hoare 的方法有效。 Lomuto 将数组分成三个部分；小于枢轴的元素，枢轴，大于枢轴的元素。我认为霍尔看待事物的方式不同。他将数组分成两部分；小于主元的元素，等于或大于主元的元素。我陷入的陷阱之一是 Lomuto 的分区返回主元的最终位置，而 Hoare 的分区返回主元最终位置之前的位置。这就是 Lomuto 然后快速排序的原因lo 到 p-1，而 Hoare 快速排序从 lo 到 p。可以得出的另一个推论是，如果 Hoare 的 partition 返回 i 而不是 j，那么我们会将数组分成两部分 - 从lo 到 i-1 以及从 i+1 到 hi，就像 Lomuto 所做的那样。我只花了 4 个小时就明白了这一点。