霍尔分裂陷入无限循环

Question

我正在尝试编写一个Hoare分区函数，它以数组作为输入，并用第一个元素作为pivot对其进行分区（我知道这不是一个好主意，我应该使用随机化的pivots，比如median-of-medians方法）。问题是，当第一个元素是最高的时，这个函数就会陷入无限循环，就像数组[14,6,8,1,4,9,2,1,7,10,5]。我可以看到错误，在第一次迭代外部while之后，i和{}都等于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，而{}是{}，这是不正确的，但它解决了无限循环问题。在

下一个问题是一个错误。如果要在内部循环中首先执行+= 1和-= 1，那么必须从-1，len(arr)开始，而不是{}（或者，就像你做的一样，1, len(arr)-1）。在

可能还有其他问题。但我不想在你的代码中挖掘所有可能的错误并解释它们。如果你需要的话，告诉我们我们的来源是什么，并解释你从这个来源所做的每一个转变，这样就更容易解释你哪里出错了。如果不是，那么直接将Hoare的算法翻译成Python就简单多了，然后希望您可以解决它。在

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

^{pr2}$

这里有一个简单的Python转换；唯一的变化是一些小语法（包括“exchange”的拼写方式）并将每个repeat/until转换为whiletrue/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)