Hoare 的快速排序如何工作，即使在 partition() 之后枢轴的最终位置不是它在排序数组中的位置？
How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?
所有变量名称均来自 Quicksort's wikipedia page 的 Lomuto 和 Hoare 的快速排序伪代码。
如果 p 是 partition 函数返回的值，Hoare 将他的数组从 lo 划分为 p，从 p+1 划分为 hi，而 Lomuto 将他的数组从 lo 划分为 p-1，从 p+1 划分为 hi。
我对此可能是错误的，但 Quicksort 的哲学是...
- 取子数组中的一个元素（枢轴）。
- 重新排列子数组，使主元左边的所有元素都小于主元，而主元右边的所有元素都大于主元。
- 围绕枢轴划分数组。对两个较小的 sub-subarrays 重复该过程。继续这样做，直到遇到只有一个或更少元素的数组，因为它已经排序了。
我发现 Hoare 的 partition 比 Lomuto 的更容易理解。霍尔分区只是指示我们从左端和右端开始，并不断向对方移动。如果左标记遇到大于枢轴的元素，则左标记暂停，等待右标记找到小于枢轴的元素。然后他们交换元素，这样左边的标记有较小的元素，右边的标记有较大的元素。他们一直这样做，直到他们见面。非常简单。
Lomuto 的partition，可以看作是一条蛇，由头和尾两部分组成。枢轴是固定的（我通常将最后一个元素作为 Lomuto 的枢轴）。蛇从 left-hand 一侧开始，并在最后一个元素之前停止。当蛇遇到一个小于枢轴的元素时，该元素会移动到尾巴并且尾巴的长度会增加。当发现大于枢轴的元素时，该元素将转到蛇的头部。最后，枢轴位于尾巴和头部之间。它非常清晰，但不如 Hoare 的 partition.
直观或高效（在某些情况下）
让我感到困惑的是，Hoare 分区不能确保 partition 之后的主元位置有 运行 它的路线，将是它在最终排序数组中的位置。我在 Hoare 的分区中唯一能识别的模式是 i 位于枢轴的 最终位置 并且 j 是 i 或i-1、j 和 i 是左右标记。
然而，Lomuto 的分区保证了这一点。所以，当我退一步看大局时，Lomuto 将数组从 lo 划分为 p-1 以及从 p+1 划分为 hi 是有意义的。但是，我无法理解 Hoare 如何将他的数组从 lo 划分为 p 以及从 p+1 划分为 hi，弥补他的划分不把它的支点放在正确的位置。
我一直在研究示例并自己通过 Hoare 的快速排序对数组进行排序。我想我在 Hoare 的分区算法中发现了另一个有趣的模式。这可以解释为什么 Hoare 的方法有效。 Lomuto将数组分成三个部分；小于枢轴的元素，枢轴，大于枢轴的元素。我认为霍尔看待事物的方式不同。他把数组分成两个部分；小于主元的元素， 个等于或大于主元的元素。我陷入的陷阱之一是 Lomuto 的分区 returns 枢轴的最终位置，而 Hoare 的分区 returns 恰好在枢轴的最终位置之前的位置。 这就是为什么 Lomuto 然后从 lo 快速排序到 p-1，而 Hoare 从 lo 快速排序到 p。可以得出的另一个推论是，如果 Hoare 的 partition 返回 i 而不是 j，那么我们会将数组分成两部分 - 从 lo 到 i-1 从 i+1 到 hi，就像 Lomuto 所做的那样。我只花了 4 个小时就明白了。
所有变量名称均来自 Quicksort's wikipedia page 的 Lomuto 和 Hoare 的快速排序伪代码。
如果 p 是 partition 函数返回的值，Hoare 将他的数组从 lo 划分为 p，从 p+1 划分为 hi，而 Lomuto 将他的数组从 lo 划分为 p-1，从 p+1 划分为 hi。
我对此可能是错误的，但 Quicksort 的哲学是...
- 取子数组中的一个元素（枢轴）。
- 重新排列子数组，使主元左边的所有元素都小于主元，而主元右边的所有元素都大于主元。
- 围绕枢轴划分数组。对两个较小的 sub-subarrays 重复该过程。继续这样做，直到遇到只有一个或更少元素的数组，因为它已经排序了。
我发现 Hoare 的 partition 比 Lomuto 的更容易理解。霍尔分区只是指示我们从左端和右端开始，并不断向对方移动。如果左标记遇到大于枢轴的元素，则左标记暂停，等待右标记找到小于枢轴的元素。然后他们交换元素，这样左边的标记有较小的元素，右边的标记有较大的元素。他们一直这样做，直到他们见面。非常简单。
Lomuto 的partition，可以看作是一条蛇，由头和尾两部分组成。枢轴是固定的（我通常将最后一个元素作为 Lomuto 的枢轴）。蛇从 left-hand 一侧开始，并在最后一个元素之前停止。当蛇遇到一个小于枢轴的元素时，该元素会移动到尾巴并且尾巴的长度会增加。当发现大于枢轴的元素时，该元素将转到蛇的头部。最后，枢轴位于尾巴和头部之间。它非常清晰，但不如 Hoare 的 partition.
让我感到困惑的是，Hoare 分区不能确保 partition 之后的主元位置有 运行 它的路线，将是它在最终排序数组中的位置。我在 Hoare 的分区中唯一能识别的模式是 i 位于枢轴的 最终位置 并且 j 是 i 或i-1、j 和 i 是左右标记。
然而，Lomuto 的分区保证了这一点。所以，当我退一步看大局时，Lomuto 将数组从 lo 划分为 p-1 以及从 p+1 划分为 hi 是有意义的。但是，我无法理解 Hoare 如何将他的数组从 lo 划分为 p 以及从 p+1 划分为 hi，弥补他的划分不把它的支点放在正确的位置。
我一直在研究示例并自己通过 Hoare 的快速排序对数组进行排序。我想我在 Hoare 的分区算法中发现了另一个有趣的模式。这可以解释为什么 Hoare 的方法有效。 Lomuto将数组分成三个部分；小于枢轴的元素，枢轴，大于枢轴的元素。我认为霍尔看待事物的方式不同。他把数组分成两个部分；小于主元的元素， 个等于或大于主元的元素。我陷入的陷阱之一是 Lomuto 的分区 returns 枢轴的最终位置，而 Hoare 的分区 returns 恰好在枢轴的最终位置之前的位置。 这就是为什么 Lomuto 然后从 lo 快速排序到 p-1，而 Hoare 从 lo 快速排序到 p。可以得出的另一个推论是，如果 Hoare 的 partition 返回 i 而不是 j，那么我们会将数组分成两部分 - 从 lo 到 i-1 从 i+1 到 hi，就像 Lomuto 所做的那样。我只花了 4 个小时就明白了。