霍尔分割算法的说明(Explanation of Hoare Partitioning algori

按照在许多网站给出的伪代码中，我已经写此Hoare分区算法，这需要一个阵列，所述子阵列的开始和结束索引来基于给定的枢轴进行分区。 它工作正常，但有人可以解释的逻辑，它是如何做的事情呢？ 这里的代码：

def hoare(arr,start,end):
     pivot = 4
     i,j = start,end
     while i < j:
        while i < j and arr[i] <= pivot:
            i += 1
        while j >= i and arr[j] > pivot:
            j -= 1
        if i < j:
            arr[i],arr[j] = arr[j],arr[i]
     return j    

有分区的的另一种变Lomuto算法。 它有类似的功能，但因为我不明白Hoare算法首先，我不能看出其中的区别。 任何人能解释这是怎么回事的算法，并给出了一个在这种情况下，更好的性能？

Answer 1:

我建议使用的卡和两个棋子/硬币甲板代表模拟这个i和j 。 基本上，算法完成这两件事，同时：

• 寻找到数组应该被分拆有“水桶”到左边，这个位置的右侧的正确的金额。 这是由值做i和j会议在分区的“中间”。
• 移动数组元素或向左，或中间的，这取决于它们是否是比枢轴更小和更大的权利。

这意味着，在任何时间， i是无论是在中间或左侧的它。 相反的是真正的j 。 认识到这一点，可以看到什么while循环做的就是找到那到中间的左边，但应该是在右边，反之亦然的元素。 也就是说，发现在错误的一半的两个元素。 然后，这些交换。

当i和j在中间相遇，到左边，你有被跳过的任何元素while ，因为他们比小的pivot ; 或从另一侧被交换的是，和元素因此也小于pivot 。 （反之亦然用于中间的右边的元素）。

混乱的一个可能来源是一个从零开始的数组索引可以在一个元件被认为要么点，或者两个元件之间的点。 例如指数0基本意思是“‘零’和数组的第一个元素之间”，当你访问一个元素，你拿一个下面这个位置上-使array[0]导致什么直观的第一要素阵列的。

Answer 2:

两个霍尔和Lamuto是分区算法。 分区算法在阵列中，使一切大于某一元件较小的一方和一切对其他较大结束到处移动的东西。 这可以用来快速数组排序或找到位数。

霍尔的工作原理是走向中间的两个边界，一个从左边，一个在右边。 下面的步骤是在一个循环中完成：

1. 直到它到达的东西比选择元件大左边界移动。
2. 右边界移动，直到它到达的东西比选择元素小。
3. 如果边界没有交叉，两者交换。

重复这个过程，直到边界在中间相遇。 其结果是一切较少左侧和家居更大右侧的分区。

Lomuto是一个类似的过程，但仅使用一个边界（通常是从左边往上走）。 这使得更容易实现，但略慢（具有相同的渐近复杂性较大的常数项）。

文章来源: Explanation of Hoare Partitioning algorithm