Hoare 分区在某些情况下会失败吗？

Question

正在研究 Hoare 分区问题，并意识到在左右指针同时遇到等于主元的值的情况下，Hoare 分区似乎无法正确排序项目。

例如对于数组[0,2,1,0,2,1,2,0]，如果你选择1作为主元，左右指针会同时遇到两个1，交换它们，然后继续，给出[0,0,1,0,2,1,2,2]

的错误输出

是否已知这是 Hoare 分区的问题？人们通常如何处理这种情况？

作为参考，这是我使用的代码：

def hoarePartition(nums):
    left, right = -1, len(nums) 
        while True:
            left += 1
            while nums[left] == 0:
                left += 1
            right -= 1
            while nums[right] == 2:
                right -= 1
            if left >= right:
                return
            nums[left], nums[right] = nums[right], nums[left]

Answer 1

分区的目的不是排序元素，而是拆分(a.k.a。partition) 它们分成两个非空组，一组元素小于或等于主元元素，一组元素大于或等于主元元素。（Hoare 分区允许任一组包含等于主元的元素，而 Lomuto 分区将所有等于主元的元素放在正确的组中。快速排序可以处理任何一个结果，但重要的是两个组都不为空；否则, Quicksort 可能会无限递归而无法将列表拆分成更小的部分。）

鉴于此，我们看到您的示例输出是有效的：算法在中间停止，左半部分的所有值都小于或等于 1，右半部分的所有元素都大于大于或等于 1。分区内的顺序无关紧要；对数字进行实际排序是 Quicksort 的工作。

但是，您的实施存在一些问题：

如果只有 0、1 和 2 的值，则可以与 0 和 2 进行比较。在一般情况下，您需要与枢轴元素的值进行比较。
因此，需要将枢轴选择融入您的代码中。它应该是中间的元素，如果元素个数是偶数，则应该是中间左边的元素。
你需要returnright，这表明两组之间的分裂。

Hoare 分区在某些情况下会失败吗？

Does Hoare partioning fail in some cases?

sorting

algorithm

quicksort