algorithm - 为什么递归调用快速排序的不同方式？

Question

我注意到递归调用快速排序的方式存在差异。

一种方法是

quicksort(Array, left, right)
  x = partition(Array, left, right)
  quicksort(Array, left, x-1)
  quicksort(Array, x+1, right)



  partition(array, left, right)
     pivotIndex := choose-pivot(array, left, right)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right]
     storeIndex := left
     for i from left to right - 1
         if array[i] ≤ pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right]  // Move pivot to its final place
     return storeIndex

[EXAMPLE]

这是有道理的，因为快速排序的工作原理是围绕枢轴划分其他元素，因此元素 Array[x] 应该位于其最终位置。因此范围 [left, partion-1] 和 [partition+1, right] 仍然存在。

另一种方式

quicksort(Array, left, right)
  x = partition(Array, left, right)
  quicksort(Array, left, x)
  quicksort(Array, x+1, right)

PARTITION(A,p,r)

x  A[p]    
i  p - 1    
j  r + 1   
while TRUE  
   do repeat j  j - 1   
        until A[j]  x   
      repeat i  i + 1    
        until A[i]  x    
      if i < j    
          then exchange A[i]  A[j]
          else return j

[EXAMPLE]

注意 -1 丢失了。这些似乎表明数组已正确分区，但没有单个元素位于其最终位置。这两种方式不可互换，如果我在第二种方式中输入 -1，则输入数组排序不正确。

造成差异的原因是什么？很明显是在分区方法的某处，是否与使用了Hoare算法或Lumuto算法有关？

Answer 1

除了在最小数组上操作时，这两个版本之间的效率实际上并没有太大差异。大部分工作是将一个大小为 n 的大型数组(其值与其适当位置之间的距离可能有 n 个空间)分成两个较小的数组， ，较小，即使在最坏的情况下，也不能使值偏离其正确位置。 “单向”实质上是在每一步创建三个 分区 - 但由于第三个分区只有一个空间大，它对算法的进展只做了 O(1) 的贡献。

话虽这么说，实现最后一个开关非常容易，所以我不确定为什么您的“其他方式”示例的代码没有采取这一步。他们甚至指出了一个陷阱(如果选择最后一个元素而不是第一个元素作为主元，则递归永远不会结束)通过实现在末尾消除主元元素的开关可以完全避免。我能想象的唯一情况是代码空间绝对宝贵的地方是最好使用的代码。