2

我正在尝试编写一个 Hoare 分区函数，该函数将数组作为输入，并将第一个元素作为枢轴进行分区（我知道这不是一个好主意，我应该使用随机枢轴，就像这种median-of-medians方法一样）。问题是当第一个元素最高时，这个函数会陷入无限循环，就像数组一样[14,6,8,1,4,9,2,1,7,10,5]。我可以看到错误，在外部的第一次迭代之后while，两者都i等于j10，因此循环永远继续。我应该修补哪个部分以获得预期的效果？这是代码：

def hoare(arr):
    pivot = arr[0]
    i,j = 1,len(arr)-1
    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]
    if j != 0:
        arr[0],arr[j] = arr[j],arr[0]
        return j
4

3 回答 3

2

我相信问题在于您已经将 do-while （或重复直到，用 Hoare 的术语）循环转换为 while 循环，因此它永远不会执行第一个 j -= 1。

Python 中最简单的转换应该是像这样更改两个内部 while 循环：

while True:
    i += 1
    if not (i < j and arr[i] < pivot): break
while True:
    j -= 1
    if not (j >= i and arr[j] >= pivot): break

（我在这里假设if i < j:应该在第二个while循环之外，并且所有其他初始缩进都是正确的。）

我还没有完全推理出这一点，也没有进行各种测试，但您的翻译中可能不仅仅是这个错误。您可能还需要将外部循环转换为 do-while （Hoare 实际上通过最后的检查使其显式while TRUE），但我不确定。无论如何，对于您的示例输入，修改后的版本返回9, 和arris [10, 6, 8, 1, 4, 9, 2, 1, 7, 14, 5]，这是不正确的，但它解决了您的无限循环问题。

下一个问题是一个错误。如果您要在内部循环中执行+= 1and -= 1first，则必须从 开始-1，len(arr)而不是0, len(arr)-1（或者，如您所做的那样，1, len(arr)-1）。

可能还有其他问题。但我不想深入研究你的代码，找出所有可能的错误并解释它们。如果您需要，请告诉我们我们的来源是什么，并解释您从该来源进行的每个转换，这样解释您哪里出错会容易得多。如果没有，直接将 Hoare 的算法翻译成 Python 会简单得多，然后希望你能弄明白。

这是我在网上找到的 Hoare 伪代码的副本（只是将所有制表符替换为两个空格）：

Hoare-Partition (A, p, r)
  x ← A[p]
  i ← p − 1
  j ← r + 1
  while  TRUE
    repeat  j ←  j − 1
      until  A[j] ≤ x
    repeat  i ←  i + 1
      until  A[i] ≥ x
    if  i < j
      exchange  A[i] ↔ A[j]
    else
      return  j

这是对 Python 的简单翻译；唯一的变化是较小的语法（包括“交换”的拼写方式）和将每个重复/直到变成一段时间 True/break。

def hoare(a, p, r):
  x = a[p]
  i, j = p-1, r+1
  while True:
    while True:
      j -= 1
      if a[j] <= x:
        break
    while True:
      i += 1
      if a[i] >= x:
        break
    if i < j:
      a[i], a[j] = a[j], a[i]
    else:
      return j

对于与您的签名相同的函数：

def hoare0(arr):
  return hoare(arr, 0, len(arr)-1)
于 2012-09-20T21:06:21.770 回答
1

这一行有一个错误：

while i < j and arr[i] < pivot:

它应该是：

while i <= j and arr[i] < pivot:

分区的整个代码如下所示：

def partition(a, l, r):
    pivot = a[r]
    i = l - 1
    j = r
    while i <= j:
        if i <= j and a[i] < pivot:
            i += 1
        if i <= j and a[j] >= pivot:
            j -= 1
        if i < j:
            a[i], a[j] = a[j], a[i]
    a[l], a[j] = a[j], a[l]
    return j

为什么会出现无限循环？

这里pivot选择的是 14。

因此，在执行此代码后：

while i < j and arr[i] < pivot:
    i += 1

i是 10 和j10。

现在，当这个块被执行时：

while i <= j and arr[j] >= pivot:
    j -= 1

作为a[10] < 14，什么都没有发生。因为，i等于j，没有交换发生。现在，由于最外面的循环有条件i <= j，循环不断重复。

修正会发生什么？

因此，在执行此代码后：

while i <= j and arr[i] < pivot:
    i += 1

ii是 11（因为当equals时条件仍然为真j）并且j是 10。

现在，当这个块被执行时：

while i <= j and arr[j] >= pivot:
    j -= 1

作为a[10] < 14，什么都没有发生。

现在，i是 11 和j10，所以不会发生交换。但是，最外面的循环被破坏并a[j]与pivot.

你的数组变成：

[5, 6, 8, 1, 4, 9, 2, 1, 7, 10, 14]

你可以在这里玩。它包含带有正确和错误分区方案的调试打印的代码。

于 2020-10-03T04:35:04.300 回答
1

这也有效：

key = arr[0]
i = 0
j = n-1
while i >= j:
    while arr[i] < key:
        i += 1
    
    while arr[j] > key:
        j -= 1
arr[j], arr[0] = arr[0], arr[j]
于 2021-10-19T08:59:45.690 回答