4

根据许多网站给出的伪代码，我编写了这个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算法，所以我看不出区别。任何人都可以解释算法中发生了什么，以及在哪种情况下哪个提供更好的性能？

4

2 回答 2

2

我建议使用一副纸牌和两个棋子/硬币来模拟它来表示i和j。基本上，该算法同时完成了这两件事：

  • 找到应该拆分数组的位置，以便在该位置的左侧和右侧拥有正确数量的“桶” 。这是由分区“中间”的值i和会议完成的。j
  • 将数组元素移动到中间的左侧或右侧，具体取决于它们是否小于和大于枢轴。

这意味着在任何时候，i要么在它的中间，要么在它的左边。反之亦然j。知道了这一点，我们可以看到while循环所做的就是找到一个位于中间左侧但应该在右侧的元素，反之亦然。也就是说，找到两个在错误一半的元素。然后交换这些。

Wheni和jmeet 在中间，在左边你有被 跳过的元素while，因为它们小于pivot; 或从另一侧交换的元素，因此也小于pivot. （对于中间右侧的元素，反之亦然。）

一个可能的混淆来源是，从零开始的数组索引可以被认为是指向一个元素，或者指向两个元素之间。例如，索引0基本上意味着“在'第零'和数组中的第一个元素之间”，当你访问一个元素时，你会在这个位置之后array[0]取一个 -导致直观上是数组的第一个元素。

于 2012-09-22T19:51:35.457 回答
0

Hoare和Lamuto都是分区算法。分区算法在数组中移动事物，以便小于某个元素的所有内容都位于一侧，而所有大于某个元素的内容都位于另一侧。这可用于快速排序数组或查找中位数。

霍尔通过将两个边界移向中间来工作，一个从左侧，一个从右侧。以下步骤在循环中完成：

  1. 左边界移动直到它到达比所选元素更大的东西。
  2. 右边界移动，直到它到达比所选元素更小的东西。
  3. 如果边界尚未跨越，则将两者交换。

重复此过程，直到边界在中间相遇。结果是一个分区，左边的东西少，右边的东西大。

Lomuto 是一个类似的过程，但只使用一个边界（通常从左侧向上）。这使它更容易实现，但速度稍慢（具有相同渐近复杂度的较大常数项）。

于 2017-02-09T14:53:48.347 回答