Hoare分区陷入无限循环

Question

我正在尝试编写一个Hoare分区函数，它接受一个数组作为输入，并使用第一个元素作为轴心对其进行分区(我知道这不是一个好主意，我应该使用随机化的轴心，就像median-of-medians方法一样)。问题是当第一个元素是最高的时候，这个函数会陷入无限循环，就像数组[14,6,8,1,4,9,2,1,7,10,5]一样。我可以看到错误，在外部while的第一次迭代之后，i和j都等于10，因此循环将永远继续。我应该修补哪一部分才能得到想要的效果？代码如下：

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

Answer 1

我认为问题在于您已经将do-while (或者用Hoare的话说是repeat-until )循环转换成了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，arr为[10, 6, 8, 1, 4, 9, 2, 1, 7, 14, 5]，这是不正确的，但它解决了无限循环问题。

下一个问题是off-by-one错误。如果要先在内部循环中执行+= 1和-= 1，则必须从-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的简单转换；唯一的变化是较小的语法(包括"exchange“的拼写方式)，并将每个repeat/until转换为while 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)

Answer 2

这一行有一个错误：

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，j是10。

现在，当执行此块时：

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

i为11 (因为当i等于j时条件仍然为真)，j为10。

现在，当执行此块时：

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

作为a[10] < 14，什么都不会发生。

现在，i是11，j是10，所以不会发生交换。但是，最外层的循环被打破，a[j]与pivot互换。

您的数组将变为：

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

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

Answer 3

这也是可行的：

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]